Deformable Butterfly: A Highly Structured and Sparse Linear Transform
Authors: Rui Lin
Jie Ran
King Hung Chiu
Graziano Chesi
Ngai Wong
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deformable Butterfly
Linear transform
Model compression

Abstract: We introduce a new kind of linear transform named Deformable Butterfly (DeBut) that generalizes the conventional butterfly matrices and can be adapted to various input-output dimensions. It inherits the fine-to-coarse-grained learnable hierarchy of traditional butterflies and when deployed to neural networks, the prominent structures and sparsity in a DeBut layer constitutes a new way for network compression. We apply DeBut as a drop-in replacement of standard fully connected and convolutional layers, and demonstrate its superiority in homogenizing a neural network and rendering it favorable properties such as light weight and low inference complexity, without compromising accuracy. The natural complexity-accuracy tradeoff arising from the myriad deformations of a DeBut layer also opens up new rooms for analytical and practical research. The codes and Appendix are publicly available at: https://github.com/ruilin0212/DeBut.

Deformable Butterfly: A Highly Structured and Sparse Linear Transform
Rui Lin li+
Jie Ran
King Hung Chiu² Grazinao Chesi!
Ngai Wong 1M
Department of Electrical and Electronic Engineering.
The University of Hong Kong, Hong Kong
Emial Address: {linrui, jieran, chesi, nwong) hku hk
2 United Microelectronies Centre (Hong Kong) Limited, Hong Kong Science Park, N.T., Hong Kong Emial Address: khchiu@umechk, com
Abstract
We introduce new kind of linear transform named Deformable Butterfly (DeBut) that generalizes the conventional butterfly matrices and can be adapted various input-output dimensions. It inherits the torttto-orre-ggrinnne learnable hierarchy traditional butterflies and when deployed to neural networks, the prominent structures and sparsity in DeBut layer constitutes pression. We apply DeBut as a drop-in replacement of standard fully connected and convolutional layers, and demonstrate its superiority in homogenizing neural network and rendering it favorable properties such as light weight and low inference complexity, without compromising accuracy. The natural complexity-accuran tradeoff arising from the myriad deformations of a DeBut layer also opens up new rooms for analytical and practical research. The codes and Appendix publicly available at: https://gihub..oomuulnnnt B2tDeBut.
way for network com-
Introduction
The linear mapping in deep neural networks (DNNs) are mostly realized in the form of fully connected (FC) or convolutional (CONV) layers. These layers, together with feed-forward feedback paths and nonlinear activations, then induce a plethora of neural architectures such as multilayer perceptrons (MLPs) [29, 23, 12], convolutional neural networks (CNNs) [11, 18, 31, 32], recurrent neural networks (RNNs) [3, 13, 30] and Transformers [33, 9]. just to name few. Although latest researches have designed and constructed highly capable networks (such the GPT-3 [1]). the nature of DNNs still remains largely black-box and inaccessible due to its extreme nonlinearity. In fact, even the seemingly trivial linear transform can become rather non-trivial when structures are imposed. Prominent examples are the Fast Fourier Transform (FFT) and convolution operators which can be cast as linear mappings and formulated as matrix multiplications. Yet they are distinguished by their underlying butterfly and circulant structures, respectively, that act as strong structural priors and lead to very distinct behaviors.
Nonetheless, relatively little attention has been paid to deriving adaptable, or even better, learnable and structured fast linear transforms in DNNs. Among the works compactly parametrize an FC layer in a DNN, a representative method is called the Fastfood Transform [20] that belongs to the category kernel methods [4, 26] and employs random projection for feature learning. In particular, Fastfood uses Hadamard transform combined with diagonal Gaussian matrices to approximate Gaussian random matrix. Adaptive Fastfood [34] further allows those diagonal matrices become
RL, JR, and NW contributed equally to this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

learnable, thus achieving better approximation of an FC layer during backpropagation. Recently, learnable butterfly matrices are also proposed [5, 6] and demonstrated be an effective FC substitute delivering high accuracy with much fewer parameters owing to the highly sparse butterfly factors. However, all these aforementioned schemes are restricted to powers-of-two (PoT) construction and thereby square structures, in which unequal input-output dimensions are handled simply by stacking square matrices followed by ad hoc dropping of inputs/outputs. Moreover, all these works aim at replacing only one or few largest FCs in a neural network, which may not yield a significant compression in the overall number of weight parameters especially in modern networks having a majority of CNN layers. Even worse, the training time of such FC replacement may end up prohibitive (cf. Experimental Section) as constrained by the high- -igh-iimensionll square matrices.
On the other hand, the proliferation of machine learning and artificial intelligence (AI) in recent years has spawned the era of edge Al whereby the DNN inference, and sometimes its training, are performed on edge devices with limited compute and storage resources. Numerous researchers have looked into compacting neural networks. In general, modern neural network compression techniques mainly fall into three categories, namely, low-rank matrix/tensor decomposition (e.g.. [25, 16, 27D, weight and/or CNN filter pruning (e.g., [10, 22I) and low bitwidth quantization (e.g., [14, 28, 2, 24]). To this end, network compression via sparse and structured matrix factorization does not fall into any of these categories, and constitutes a new yet under-explored way of neural network compression. As revealed in [5], such structured and sparse matrix factor chains (such as the FFT butterflies) are often accompanied by fast inference due to their recursive nature and the availability of fast matrix multiplication schemes [7].
Subsequently, this paper attempts to kill two birds (viz. learnable factorized linear transform with structured sparsity and flexible input-output sizes) with one stone by introducing a novel linear transform named deformable butterfly (DeBut) that generalizes the square PoT butterfly factor matrices [5, 6]. Specifically, DeBut product chain (or simply a DeBut chain) can be sized to adapt to different input-oulput dimensions. For one thing, it does not limit itself to PoT blocks as in Fastfood Transform or butterfly matrices [20, 34, 5, 6]. Moreover, the intermediate matrix dimensions in DeBut chain can either shrink or grow to permit a variable tradeoff between number of parameters and representation power. The flexibility of tuning the dense matrix sub-block: in DeBut also permits an interpretation similar to the CNN receptive field for exploiting locality and correlation in data. In fact, as will be shown in experiments, DeBut chain does not distinguish CONV FC layers, and can be used as a substitute of both while maintaining a high output accuracy. To our knowledge, the DeBut linear transform is proposed for the first time, and this work is starter to showcase its use in DNNs which we hope can provoke further theoretical and practical insights.
2 Background
2.1 Butterfly Matrix
DeBut is inspired by the learnable butterflies proposed in [5] and its subsequent Kaleidoscope matrix extension [6] (called K-matrix) which is essentially a butterfly matrix multiplied to another transposed butterfly matrix. The learnability and efficacy of K-matrices are then demonstrated in several applications including: 1) replacing handcrafted features in speech preprocessing and CNN channel shuffling: 2) learning latent permutation to "unpermute" scrambled pixels in an input image; 3) speeding up inference in the linear layers in Transformer translation model. The schemes and examples in [5, 6], however, employ only the conventional square PoT butterflies and substitute only one or several big FC layers in DNN.
To ease illustration, Fig. shows the four butterfly factor matrices for 16 16 case. Specifically, we adopt an information-flee flow viewpoint for explaining this butterfly hierarchy. To begin with, the rightmost input vector is partitioned into 16 individual entries. It can be seen that after going through the first matrix-vector product, every pair of entries are "mixed" by the 2 x 2 diagonal sub-blocks so that the output vector is partitioned in pairs meaning that, e.g., the top two entries now contain information from the top two individual entries in the original input vector and so on. Following this convention, one can see that the butterfly matrix product represents a progressive, stage-by-stage information mixer such that after the final matrix-vector product, each entry in the leftmost output carries the merged information from all individual entries of the rightmost input, thus corresponding to coo--coare-ggainnn abstraction advancing from factor to factor through the butterfly chain.

---

Merged Information
Information Flow
Individual Entries
R(2288)
R(2244)
(2222)
(16,66) R (222.1)
Figure 1: 16 16 Butterfly factor matrices and the hierarchical information flow from right left, where the blue squares stand for nonzeros and the numbers in the vectors denote the positional indices. The dashed lines, which connect the DeBut factor and the vector, mark the entries that will be mixed up in the vector and the corresponding sub-block in the DeBut factor that works as the mixer. The partitions the vectors denote the merging information (cf. Section 2).
Filter
C,
Input tansor
Output tonsor
H.W.
H.
W.
Equivalent GEMM appreach
W
G (ca). Hinput (output) channels
& kernel spatial size
H, (H.). input (output) height
(W.): input (output) width
DeBut substitute of
Flattened filter matrix /'
(b)
(c)
Figure CNN convolution in its (a) conceptual, illustrative form; (b) equivalent matrix-mann mmarix implementation by a flattened kernel matrix; (c) DeBut replacement of the kernel matrix.
2.2 Convolution as a Matrix Product
The convolution operation in CNN often conceptually depicted as window kernel sliding across the Ca-channel input feature, exemplified in Fig. 2(a). In practice, however, it is seldom realized this way due the inefficient nested for-loop operations. Rather, it often proceeds by the highly optimized matrix-matris product at the expense of larger memory footprint due to the extra data entries generated by the im2col command. Specifically, this command stretches the entries involved in each filter stride into a column and concatenates the columns into flattened k2cc x H.W, matrix, depicted in Fig. 2(b). One interesting remark is that FC layer is then equivalent setting the kernel spatial size to be exactly the same that of the input. Then, each output node in the FC corresponds a one-step filtering (viz. without sliding/stepping) by the H, W; X c; filter on the input tensor, as shown in Fig. 3. Consequently. both CONV and FC layers can be unified under this im2col notion whose difference lies only in the setting of the kernel spatial sizes yielding different formations of the corresponding flattened filter matrix F.
3 Deformable Butterflies
Building upon the success of butterfly-hased FC layer approximation [5, 6] (more precisely PoT butterfly substitute since fine-tuning entails newly learned layer instead of approximation), the

---

Tepart
Oxigut
R 612 (23.1)
Nor- element
Equiralent GEMM appreect
R (12,12)
R(12.19)
(3,32)
(2333)
Flanezed Gher manis
Dullut
saboliute of
Figure 3: Convolution equivalent of FC.
Figure 4: Example DeBut factors.
central innovation and contribution of this work lie in the formulation of a DeBut chain that plays the role of F in in Fig. 2(c) and subsequently that in Fig. 3. However, different from [5, 6]. DeBut chain is 1) not necessarily PoT blocks or square; 2) not intended as approximate, but rather replacement, to the circulant or doubly circulant structure adhering to CNN convolution; and 3) not of 3B construct (B being the set of butterfly matrices) as the K-matrix [6] which doubles the amount of parameters to be learned.
We define the notion of real-valued DeBut factor (r.ad E _2xx that contains block matrices along its main diagonal, wherein each block matrix is further partitioned into blocks of diagonal matrices. Fig. 4 shows several DeBut factor structures. This notational convention comes in handy distill several important properties:
Number of (not necessarily square) diagonal block matrices is rt which also equals 2;
Number of parameters (blue squares in Fig. 4), also loosely called number of nonzeros though they still be zeros by learning, is ps which also equals gr.
With this notion in hand, the 16 x 16 butterfly factor matrix product in Fig. can be expressed as
B
((16,16) ((22,4))
( ((22.1)
For brevity we also use the following shorthand for (1)
16 (2,2,8)
16
16
16
16.
(2,2,4)
(2,2.2)
(2,2,1)
A closer look reveals that in this standard butterfly chain the changing variable is the diagonal block
size in PoT steps of 1, and 8. Another important observation of the butterfly factor chain is the progressive and hierarchical aggregation of information. This is reflected in the densification of intermediate products into dense diagonal blocks. Taking the standard butterflies Fig. and (1) for example, such densifying process, namely, producing ((P-9) (r.8.1) with r x dense sub-blocks, can be
seen in the partial products in (1):
(16.16) (2,2,8)
R (2224
R (16.166
(2,2,2) (2.2.1)
(16116)
(3)
(10.16)
(4.4.1)
(10.10)
(16.16.11
where the dense sub-blocks below the underbraces appear in the order ((2.21)) (16,16) (166616))
(1.4.1)
(16.16) and R 166. In essence, such densification flow can be generalized to deformable blocks arising
from the product of two contiguous DeBut factors, with diagonal sub-blocks (t > 1) and another

---

A Bulging Chain
128
256
-12
640
400
(2.4. 64)
(2. 32)
(4. 5,
(8. S. 1)
R (610,100) (8.5.1)
Matrix Multiplication of all Matrices between Dashed Lines
RP (502 (32,25.1)
(256,000) (64.100.1)
R
(128,400)
(128,400.1)
R with dense bub-blocks
Figure 5: A bulging DeBut chain (not drawn scale) and its densification process from right to left.
The yellow, blue, and teal in the plots denote +1, -1 and O, respectively.
22(22-9a) (2(P1-0))
with dense sub-blocks (t = 1), say (22) (11.9111) where i2 > 1. It can be further shown that such densifying product mandates = P1 and l2 = T1, leading to:
R(Pa.0)) (19.1.0291.1)
((Pa)))) ((P1.))) (12.02.r1) (m1,811)"
(4)
Next, we analyze the complexity of evaluating a DeBut product chain versus the matrix-matrix multiply in Fig. 2(b). We emphasize that such a comparison is made from a purely mathematical viewpoint without considering specific hardware optimization. Specifically,, when given CONV layer with 4-D kernel tensor of size [ct, Co, k, k] and an input feature tensor of size [ct, H4, W.]. the complexity of convolution via General Matrix Multiply (GEMM) is Occ, k²c; H,W.). H.W.), where N is the number of DeBut factors, and max (1,.. .N3 P;S; denotes the number of nonzeros in the DeBut factor containing the most nonzeros. It is worth noting that evaluating a DeBut chain has much lower complexity compared with GEMM, attributed to the exponentially fewer total number nonzeros from all DeBut factors. Detailed expositions of the densification condition and additional complexity analysis can be found Appendix! I.
while that of DeBut is ((max;e (1.... P:8;-
3.1 Designing DeBut Factors
Now we are ready to present the core step of replacing the matrix F E &R by appropriately sized DeBut chain. Again, the best way is illustrate through number example. For this purpose. we choose the biggest FC layer in modified LeNet (cf. Table 1) wherein the flattened F measures 128 x 400. Apparently, in going from the input to output, the input vector dimension (400) has to be shrunk to that of the output (128). In this regard, there multiple choices for the DeBut chains as long as 1) the "boundary" dimensions are met: and 2) the densifying condition in (4) can be satisfied throughout the chain (see (3)) so that the final product B does not contain any "voids" (zeros), else some input entries will be nullified causing incomplete information flow.
In particular, because of the deformable nature of a DeBut factor, we can devise monotonic (monoton- (expand-then-shrin then-shrink) chains that feature different number of parameters and accuracies. For example, Fig. 5 shows a bulging chain and its corresponding densi- fication process. In this example, we set every nonzero be random +1 -1, i.c, bipolar. Then, it can be traced through the chain and verified that every dense block in the product accumulation (including the leftmost final product Fig. 5) also bipolar. We call this "bipolar test" for checking the integrity of information flow, which essentially means that no entry in the linear transform is forced zero by an ill-posed DeBut chain. Analogous to the myriad of choices in CNN filters, we solicit insights and guidelines for picking effective DeBut chains in the experimental section.
ically shrinking or expanding) or bulging (expand
3.2 Initializing the DeBut Factors
If we have a pretrained network whose F' matrix (see Fig. 2(b)) is already available, then is possible to initialize the DeBut factors by approximating their product to F. Here we describe an alternating least squares (ALS) scheme to initialize these factors such that their product stays close to F' in the 2-norm sense. Specifically, for given F' and starting with randomly initialized DeBut chain
5

---

LoNet
Weights
Ourguts
VGG
Weights
Chiputs
[Ta fas
IPus kfee)
Wol
[Cox [g
CONVI
1.8.3.3]
8. 26,
CONVI
3. 64,
27]
[64. 32]
8. 16,
[16. T1
11, 11]
CUNV2
64,
676]
664. 32]
RC1
16. 128, 5,
1128, 400]
128,1 1]
CONVI
64. 128, 3,
128, 576)
125. 16, 16
PC2
128. 64, 1.
(64, 128]
[64, 1
CONV4
128. 125.
3. 3]
128. 1152
125. 16, 16
KC3
10.1.
[10,
CUNY5
2288, 3.
226..
16,16)
256. 256.3,
256. 2304
2656, 8
CONV?
2566, 256, 3
256, 2304
2266, 8
CONV8
256, 5,2,3,3
512. 2304
256 6.8
CONV
012.612.3.5
512.
512. 3,2
612. 4608
512,4.
CONVIL
512,512,3,3
512, 4608
512, 4,4
CONV12
512. 512, 3.3
512, 4608
512. 4, 4
CONV13
512. 612. 3.3
G12.
RCI
512, 512,
612, 512]
5122 1.
PC2
512,
10,
1,
11
612, 10)
p0. 1,
Table (Left) The modified LeNet with baseline accuracy of 99.29% % on MNIST. (Right) VGG-16- BN with a baseline accuracy of 93.96% on CIFAR-10, 10. In both networks, the activation, max pooling and batch normalization layers are not shown for brevity.
wherein one of the factors is M. first multiply all factors on the left of M and lump them into L, and similarly for on the right. If M on the left/rightmost. then we assume an identity matrix its left/right. Now, we use toy example for the ALS illustration, whose generalization is straightforward. Note that all notations in this subsection are local and not to be confused with other sections. Suppose we have 4 x 4 M with eight may" 's in the example below,
1/11
71
F=
0
11222
0
17424
R.
(S)
0
71133
O
0
7742
0
1714
Using Matlab-style notation for a row/column, simple algebra shows F can be broken into eight rank-1 factors Lamy Ry. Utilizing the Kronecker product property vee( Lammi Rz.) = R2. @ Lamay. we then have the LS approximation of may" 's being the solution of the linear system
m11
ma1
vec(F)= = (R.. & L.1
RT. 8 La)
(6)
:
We note the matrix preceding the unknown vector is a Khatri- product (i.e. column-wise Kronecker). Once M is solved, then we advance to its adjacent factor and repeat the same procedure. In short, ALS entails sweeping the chain back and forth until the residual error no longer decreases. In our experiments, the ALS consistently converges within only a few sweeps.
4 Experiments
We test the proposed DeBut chains on LeNet (Table 1, left), VGG-16-BN (Table right) and ResNet- 50 [11] using the standard MNIST [21], CIFAR-10 [17] and ImageNet [8] datasets, respectively. The results are presented in the subsections below. Since DeBut a superset of the (square) Butterfly and Kaleidoscope matrices in [5, 6]. we do not repeat their specific applications. Rather, our primary goal to validate the use of DeBut chains in substituting FC and CONV layers in a DNN, and to borne out important insights and design guidelines. In Section 4.4, we contrast DeBut with its closest and most practical linear transform work named Adaptive Fastfood [20]. The results further demonstrate the superiority of DeBut.
Implementation details. In our experiments, we compare the results of DeBut factors with and without ALS initializations. Note that ALS is only applied once prior to training, so to initialize a DeBut chain as an approximate of a pretrained layer (viz. F), if the latter is available. We set the number of sweeps equal to 5 when initializing relatively small layers (viz. all layers in LeNet, and CONV1~3 and FC1 in VGG- VG--16-BN). Whereas the number of sweeps set to 10 for larger layers in VGG-16-BN and ResNet-50. The convergence speed of ALS initialization is presented in Appendix II (Fig. A1). When training the neural networks after substituting the selected layers by DeBut chains, we use the standard stochastic gradient descent (SGD) for fine-tuning, We remark that

---

the layers that are not substituted by DeBut factors have pretrained parameters instead of randomly initialized ones. On MNIST and CIFARIO datasets, the learning rate is 0.01 with a decaying step of 50, the batch size and the number of epochs are set to 64 and 150, respectively. As for ImageNet training, the decaying step 30 and the training warms up in the first epochs. The batch size and the number of epochs are 128 and 100, respectively. All coding is done with PyTorch, and experiments run on an NVIDIA GeForce GTX 1080 Ti Graphics Card with 1IGB frame buffer. This also shows DeBut networks can be readily trained using very decent resources.
4.1 LeNet Trained on MNIST
We first test the proposed DeBut structure on the modified LeNet shown in Table (left column) whose baseline accuracy is 99.29%. As described in Section 2.2, a FC layer can be regarded as a CONV layer with its kernel spatial size equal to that of the input. To quickly zoom into the benefits of DeBut, we pick the two biggest FC layers ([128,400) and (64,128) and the largest CONV2 layer (116,72) and substitute them with DeBut chains. We devise monotonic chains with both fast and slow shrinkage, as well results are listed in Table 2 which shows DeBut plug-in for three cases: FCI only, CONV2 only and CONV2+FCI+FC2. We define layer-wise compression (LC) and model-wise compression (MC) as the amount of reduced (i.e. zeroed) parameters in a DeBut layer with respect to the number of parameters in the original layer and the number of parameters in the whole network, respectively. When computing LC, we take account of the local FC or CONV layer only, in which bias are included. As for the MC metric, the global model is considered, including parameters of bias and BN layers. Apparently, the higher the LC or MC the better. Additional experiments using different monotonic and bulging chains provided in Appendix III (Tables A1 and A2).
few bulging chains with different bulge sizes and shapes. Their
We note that a CONV layer is already a significant parametric reduction from an FC layer, yet DeBut is still able to reduce the number of parameters further while delivering promising output accuracy. In this small example, ALS initialization not always beneficial for learning the latent information, but its advantages will become obvious in larger examples to follow. Interestingly, this echoes the unimpressive results of Adaptive Fastfood vs the original mno-adappive) Fastfood in small examples, in which the former excels significantly in larger models [34].
Layer
BougioniccBulgiigg Chains
LC
MC
Parmms
Accf (no ALS)
Acc% (w/ ALS)
FCI
(1,2,33)
256
(2,2.16)
256
(16,25.1)
400
85.00%
70.78%
17.96K
98 98.89(=0.08)
98. 98.72(#0002)
128
128
(2.2.64)
(2.2.32)
CONV2
16
16
48
96
72
41.67%
1.04%
60.84K
99.02 (9.02(()0066) 98.66(10.002)
(2:2,8)
(2.0.4)
(1.2.4)
(4.3.1)
CONV2
16
48
96
41.67%
(2.0,8)
(1,2,8)
(2.2.4)
(4,3,1)
FCI
(1,2,32)
256
(2.3.10)
256
(16,25.1)
400
85.00%
83.43%
10.
98.64(20.16) 97.27(#0.02)
128
128
128
(2.2.04)
(2.2. 92)
FC2
(2.2.8)
64
(2,2.4)
64
(2.2.2)
64
(2.4.3)
128
80.06%
(2,2,32)
(2,2,18)
Table 2: DeBut substitution of single and multiple layers in the modified LeNet. LC and MC stand for layer-wise compression and model-wise compression, respectively, whereas "Params" means the total number of parameters in the whole network. These notations apply to subsequent tables.
4.2 VGG Trained on CIFAR-10
After verifying the efficacy of DeBut layers in the small LeNet example, we move on to a larger network. Specifically, we train a VGG-16-BN network (Table 1, right) on CIFAR-10 which is variant of the original VGGNet [22] and has baseline accuracy of 93.96%. We first substitute the last CONY layer (CONV13) with DeBut layer to quickly see its effect. As shown in Appendix IV (Table A3). three monotonic and three bulging DeBut chains are designed, initialized either randomly or with ALS, to test their performance. All the chains achieve remarkable LCs in CONV13, with only little drop in accuracy when using ALS initialization. Besides, one of the monotonic chains, listed in Table 3, has an MC of 15. 23% while achieving a prediction accuracy of 93.91% % which very close to the baseline.
7

---

Recalling from Table 1, CONV9~13 have an F of the same size [512, 4608). Apparently, it is time-consuming to trial different DeBut chains each layer and pick the best chain combination across multiple CONV layers. Instead, we select proper Debut chain structure and assign it to layers of the same size. Amid our tests of different chains the same layer (Appendix IV, Tables A4 & A5), we have observed that a bulging chain will generally yield smaller ALS error, attributed to its bigger number of parameters. However, bulging chains with more nonzeros may not necessarily lead to better (re)trained accuracy than their monotonic counterparts. To the contrary, the latter tend to behave more stably in the training process and can often achieve a higher final accuracy. Subsequently, deploy monotonic chain with the least ALS error to obtain high compression and accuracy simultaneously. In Table 3, all CONV layers with 512 output channels (CONV8~13) replaced with DeBut monotonic chains. Amazingly, this VGG-16-BB BN with DeBut layers achieves a remarkable MC of 83.77% with only a slight 0.24% accuracy drop.
Layer
Chaia(s)
MC
Partus
Acc% (w/ ALS)
4096
CONVI3
(2,2,16)
(2:2,8)
(8.9.1)
96.79%
15.23%
12.71M
93.91(=0.08)
1024
2048
4096
(2,4,256)
(3,4,125)
(2,4,64)
(2,2,32)
2048
2048
2048
2048
2304
CONVE
(2,2,32)
(2,2,18)
(2,2,8)
(6,8,3)
986
79%7
512
1024 (2,4,126)
(2,2,256)
(2,4.84)
83.77%
2.43M
93.72(10.07)
4096
4096
4096
CONV9~113
(2,2,16)
(3,2,8)
(8,0.1)
96.79%
512
1024
2048
4096
(2,4,256)
(2,4,128)
(2,1,61)
(9,2,39)
Table 3: DeBut substitution of single and multiple layers in VGG-16-BN.
4.3 ResNet-50 Trained on ImageNet
Next, examine the effectiveness of DeBut layers using ResNet-50 trained ImageNet which a much larger and more complicated dataset than both MNIST and CIFAR-10. 10. In particular, we use DeBut factors substitute the CONV layers (9 in total) in the last three bottleneck blocks. The chain details in each layer are described in Appendix V (Tables A6 & A7). As an ablation study, we employ sets of chains, one containing only bulging chains (DeBut-buuling) whereas another contains only monotonic chains (DeBut-mono). The two sets of chains have different properties. For the set of bulging chains, their ALS errors are smaller and therefore can approximate the layer-wise F more accurately. However, bulging chains have lower compression due to additional parameters compared with monotonic chains.
The results are listed in Table 4. For DeBut-bulging the number of parameters reduces by 47.56% the t accuracy is 74.52%, 1.49% lower compared with the baseline of 76.01% %. For DeBut-mono, the compressed model has 0.3. fewer parameters than the DeBut- bulutbbuiiig model, yet still achieving comparable 74.34% top-1 accuracy.
Model
MC
Params
Top 1(%) with ALS
Top- with ALS
ResNet-50
76.01
92.93
DeBut-bulging
47.56%
13.40.M
74.52
92.18
DeBut-mono
48.74%
13.10M
74.31
92.31
Table 4: Results of ResNet-50 on ImageNet. DeBut chains are used to substitute the CONV layers in the last three bottleneck blocks. The DeBut chains used are described in Appendix V (Tables A6 & A7).
4.4 Comparison
4.4.1
DeBut vs. Other Linear Transform Schemes
We further contrast DeBut against the original Butterfly [5] and Adaptive Fastfood [34] on MNIST and CIFAR 10. The comparison on the ImageNet dataset is not included since Fastfood training is impractically time-consuming on large datasets. The results reported of Butterfly are our implemen- tation using their officially released codes. As for Adaptive FastFood, we obtained the results by
8

---

modifying the official codes of Fastfood available in sklearn (we remark that the sklearn codes are the fastest implementation we could find), Therefore, the comparison is fair as all algorithms are compared in the standard coding and software environment.
In Table 5, do both single-layer and three-layer replacement the modified LeNet and apply different economic linear transforms. Although Adaptive Fastfood has both good accuracy and high compression, it suffers from two major limitations. First, this method only supports PoT input-output sizes, But even more restrictive is the computational complexity of Adaptive Fastfood that scales at On log where n is the dimension of the input vector. As discussed in Appendix I, the complexity of DeBut is ON max; (1,.., .N) 9:7;) where N is the number of factors in a DeBut chain. When replacing FC and CONV layers, r; a small number, N I log n and q: S n since we do not expand the input size larger number than 2 20oogn) ml Subsequently, the complexity of DeBut is lower than (n no. Additionally, large batches of data are needed in training, for which Adaptive Fastfood performs repetitive Fast Hadamard Transform (FHT) while DeBut only needs tensor element-wise multiplication. In practice, the FHT is exceedingly time-consuming and makes it difficult to train Adaptive Fastfood on multiple layers in a large CNN.
Table showcases the effectiveness of DeBut versus the other two methods. It can be seen that DeBut achieves the highest prediction accuracy with only 0.3M more parameters. We also note that Adaptive Fastfood takes around 2100s for each training epoch, making its training prohibitively slow even just for CIFAR-10.
Layer
Method
MC
Acc'i
Adaptive Fastfood
80.78%
11.82K
98.85 98.89( 10.07)
FCI
Butterfly
68.29%
19.50K
98.64( =0.09)
DeBut
70.78%
17.96K
98.8 08.89(=0.08)
Adaptive Fastfood
94.73% 79.75%
3.2K
(8.61()).08)
CONV2 & FCI & FC2
Butterlly
12.45K
98. 98.02(
DeRut
83.43%
19.
98.64(=0.15)
Table 5: Comparison results for LeNet MNIST. For DeBut, the chains for the corresponding layers are the same as in Table 2.
Layer
Method
MC
Params
Acc%i
Training Time(sfepach)
Inference Time(s)
Adaptive Fasifood Buttertly
85.65%
2.15.M
(3.60(==.00)
2100
148.25
CONV8~13
82%
2.13M
93.34(=0.12)
105
1.58
DeHut
83.77%
2.43M
93.72(=0.07)
50
4.01
Table 6: Comparison results for VGG-16-BN on CIFARIO. For DeBut, the chains for the correspond- ing layers are the same as in Table 3.
4.4.2 DeBut vs. Conventional Compression Schemes
Besides comparing DeBut with its closest schemes (i.e., Butterfly [5] and Adaptive Fastfood [34]) in Section 1,4.1, also discuss the relations between DeBut and the popular compression schemes, namely, quantization, pruning and low- rank decomposition to further benchmark the dif- ferences between DeBut and existing approaches.
Layer
Method
Params
Acc(%)
Baseline
14.99 4.999M
93.96
13
Tucker-2
3.21M
93.36 23.36
DeBut
2.43M
93.71
Comparison results between DeBut and Tucker-2 for VGG-16-BN CIFAR10. The chains for DeBut layers are the same as in Table 3.
Table 7:
For weight quantization and pruning, we stress that DeBut is orthogonal and complementary to them, which means DeBut can be readily plugged in to compress further the compact models obtained by them. Therefore, we do not compare DeBut with quantization and pruning.
When compared with low-rank decomposition, it is worth noting that all matrix factors in given DeBut chain are full-rank, and therefore the chain product as well. In addition, none the tensor decomposition approaches (e.g., tensor train, Tucker, CP decomposition, etc.) show low-rank structures in DeBut. short, DeBut is brand-new way of structural matrix factorization with high sparsity and does not belong to the class of low-rank matrix factorization. In Table 7, compare

---

DeBut with a classic low-rank decomposition method called Tucker-2 [15], it can be observed that DeBut achieves better performance than Tucker-2 (93.71% vs. 93.36%) with even fewer number of parameters (2.43M vs. 3.21M). This result demonstrates that DeBut has comparable or even better compression ability than low-rank decomposition approaches.
Additional Remarks
few important remarks are order:
DeBut layers are truly practical and can be realized for ImageNet-seale datasets and networks using standard resources, where other fast linear transform schemes fail due prohibitive training and inference times.
Both Winograd [19] and FFT are algorithmic-leve acceleration of CONV operation, and are mathematically equivalent to convolution. The methods in [5, 6] are also fitting butterfly structures onto the circulant matrices or FFT butterflies corresponding to CNN convolu- tion. To this end, DeBut is fundamentally different as it is neither reformulation nor an approximate of CONV, but brand new structural regularizer of its own.
A beauty of DeBut layers is that they further unify and homogenize FC and CONV layers in the sense that DeBut is doing this linear mapping in its unique butterfly-like attribute that alleviates the PoT limitation with reduced complexity than dense matrix multiplication. Indeed, CONV and FC only differ in their ways of aggregating information which is analogous sizing the receptive field in CNN kernel, as shown in Figs. 2 & 3. This maneuver can also be controlled by juggling the dense block size in the rightmost DeBut factor chain.
The reason for having both types (bulging and monotonic) of DeBut chains is threefold: compression ability, performance, and stability. Although monotonic chain can obtain a more compact and robust model, a bulging chain is expected to have better performance since in principle it has a higher representation power and may learn better latent information. Therefore, we need both types of chains to meet different model requirements. Since this article's key innovation the new DeBut structured matrix factorization and not the enumeration of chains, we will provide more chain designing details in our upcoming work.
The progressive, hierarchical flow in the DeBut factor product chain provides an important implication for a pipelined DNN inference speedup, namely, the linear mapping is broken into multiple phases of granular (and cheap) matrix products whose intermediate results can be pipelined for overall speedup. This will be pursued in future work.
6 Conclusion
This work literally thinks out of the (square) box to introduce new class of unnecessarily square, deformable butterfly (DeBut) factors that are verified to be economic substitute CONV and FC layers without sacrificing accuracy. The inherent structured sparsity in DeBut chain naturally gives rise to a mme-tto-coarse-gaainee hierarchical mapping, as well as versatile way to achieve network compression. Experiments have shown the superiority of DeBut linear transform over competing algorithms, especially for large networks where the training and inference complexities matter. is expected more interesting theories and practical insights will arise when the DeBut layer is coupled with other application-speccfie networks and/or optimization schemes.
Acknowledgement
This work is supported in part by the General Research Fund (GRF) project 17206020, and part by the in-kind support of United Microclectronics Centre (Hong Kong) Limited.
10

---

References
[1] Tom B Brown, Benjamin Mann, Nick Ryder. Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
[2] Jian Cheng, Jiaxiang Wu, Cong Leng, Yuhang Wang, and Qinghao Hu. Quantized cnn: A unified approach to accelerate and compress convolutional networks. IEEE transactions neural networks and learning systems, (9(10)4433-44445 2017.
[3] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre. Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder- decoder for statistical machine translation. arXiv preprint urXiv: 1078, 2014.
[4] Youngmin Cho. Kernel methods for deep learning. PhD thesis, UC San Diego, 2012.
[5] Tri Dao, Albert Gu, Matthew Hichhorn, Atri Rudra, and Christopher R&eacute, Learning fast algorithms for linear transforms using butterfly factorizations. Proceedings of machine learning research, pages 1517-1527, 2019.
[6] Tri Dao, Nimit Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszczynski, Atri Rudra, and Christopher Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. In International Conference on Learning Representations, 2020. URL attps://openrevien net/ htte/forumiddd BkgrBgSYDS. dege/foourrddddBgggggSSSSS
[7] Christopher De Sa, Albert Cu, Rohan Puttagunta, Christopher Ré, and Atri Rudra. A two- pronged progress in structured dense matrix vector multiplication. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1060-1079. SIAM, 2018.
[8] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
[9] Jacob Devlin, Ming-Wai Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, NAACL-IILT (1), pages 4171-4186. Association for Computational Linguistics, 2019, ISBN 978-1-9507377-1-00.
[10] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with praning, trained quantization and huffman coding. International Conference on Learning Representations (ICLR), 2016.
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[12] Ali Asghar Heidari, Hossam Faris, Ibrahim Aljarah, and Seyedali Mirjalili. An efficient hybrid multilayer perceptron neural network with grasshopper optimization. Soft Computing. 23(17): 7941-7958, 2019.
[13] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()) 1997.
[14] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neural networks. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[15] Yong- Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Compression of deep convolutional neural networks for fast and low power mobile applications. arXiv preprint arXiv:1511.000 2015.

---

[16] Yong- Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Compression of deep convolutional neural networks for fast and low power mobile applica- tions. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR, 2016. UtR.http://arxtt org/ h/tg//ab////a 1tt./.11....1.1 06530.
[17] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[18] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-
1 1105, 2012.
[19] Andrew Lavin and Scott Gray. Fast algorithms for convolutional neural networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4013-4021, 2016.
[20] Quoe Le, Tamás Sarlós, and Alex Smola. Fastfood-ap approximating kernel expansions in loglinear time. In Proceedings of the international conference on machine learning, volume 85, 2013.
[21] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http: //yann. lecunn com/ exdb/mnit/mm.
[22] Hao Li, Asim Kadav, Igor Durdanovie, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXiv:1608.088 2016.
[23] Fionn Murtagh. Multilayer perceptrons for classification and regression. Neurocomputing, (5-6):183-197, 1991.
[24] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling. Data-free quantization through weight equalization and bias correction. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
[25] Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P Vetrov. Tensorizing neural networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[26] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008
[27] Jie Ran, Rui Lin, Hayden Kwok-Hay So, Graziano Chesi, and Ngai Wong. Exploiting elasticity in tensor ranks for compressing neural networks. In Proceedings of the International Conference on on Pattern Recognition (ICPR), 2020.
(28) Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision ECCV 2016, pages 525-542, Cham, 2016. Springer International Publishing.
[29] Dennis W Ruck, Steven K Rogers, and Matthew Kabrisky. Feature selection using a multilayer perceptron. Journal of Neural Network Computing, 2(2):40-48, 1990.
[30] Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, (1611112:673-281111 1997.
[31] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409.114 2014.
[32] Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 1-9, 2015.
[33] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, F. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
12

---

[34] Zichao Yang, Marcin Moczulski, Misha Denil, Nando De Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep fried convnets. In Proceedings of the IEEE International Conference on Computer Vision pages 1476-1483, 2015.
13


Reviews:
[{"review_id": "IlLLtvbBxy", "reviewer": "Reviewer_Nvoh", "summary": "The paper proposes \"Deformable Butterfly\" (DeBUT) a generalization of butterfly transforms (the linear operator behind the FFT), which can support non power-of-to inputs/outputs. \nIt studies how to plug such transforms into various architectures (LeNet, VGG, ResNet), from the perspective of filter design, initialization, parameter savings and accuracy loss.\nOverall it is demonstrated that DeBut can achieve a favourable tradeoff compared to previous butterfly-style approaches such as \"Buterfly\" [5,6] and \"Adaptive Fastfood\" [35].\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is very well written, with clear figures demonstrating the concepts of interests. The\npresented generalization of butterfly matrices seems very natural, and addresses the following challenges:\n\n- How to ensure that there are no \"dead parts\" in the chain of linear transforms.\n- How to go increase or decrease the number of channels (or doing both in so called \"bulging\")\n- How to initialize the transforms with an alternative least squares (ALS) method\n- How to fine tune the resulting network\n\nThe experiments are relatively extensive, and the results in Tab 4.-6. are favorable to the proposed method.\n\nMy main concerns are the following:\n\n- The relationship between the generalized butterfly transform and generalized FFT.\n It is well known the FFT (e.g. the Cooley–Tukey FFT algorithm) can recurse over any factorization of the input size, not just powers of two (POT). Is there a relationship between this and the proposed DeBUT transforms?\n- The design of the transforms seems rather complicated. It would be more convincing if the authors could present a simple rule on how to transform layers.\n- Related: there is a constraint p/r = q/s that needs to be satisfied. This implies the channels need to be prime factorizable if you want to transform them. I don't see any discussion about this.\n\n- Inference times are presented in Tab. 6, without any details. Is this exploiting the structure of the transform? Why is the baseline (original network) missing from the benchmark? \n\n- Does not seem to work without ALS initialization for large networks? I did not find the results for this, although they were said to be found in Table A3. in the appendix.\n\n- in l.104 it is said DeBut \"replaces\" the circulant structure of CNN convolution. This sounds wrong to me, as the doubly circulant structure emerges from the same matrix multiplication being applied to to each patch extracted from the im2col operation. DeBut is also doing this, so the circulant structure remains (you could say with a nested butterfly structure).\n\n\nFinal update: Given the rebuttal and the other positive reviews, I am keeping my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "68kIMcqliwy", "reviewer": "Reviewer_aaRU", "summary": "The paper present a generalization to butterfly matrices used for FC layer compression that allows flexibility in the dimensionality of the map. This removes the power-of-two limitation. Using that, the authors compress not only FC layers but also conv layers. In addition, the DeBut chain can be made flexible and serve as an addition design parameter. The results confirm that expressivity remains high under considerable compression ratios with better inference rates than competing approaches. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* I wish to compliment the authors on a very well written paper. It was clear and pleasant to follow. \n* The proposed method is elegant and practical. The experimental section shown convincing results on standard benchmarks. \n* The hierarchical structure imposed by the DeBut chain is interesting to investigate, and the different chains that can be formed allow a nice flexibility to the model design with possible trade-offs between expressivity and model size. \n\nWeaknesses:\n* I would like to see a more principled comparison of different chains and their effect on performance.\n* when applied to convolutional layers the hierarchy effectively imposes a spatial structure to grouping neighboring pixels. Could you show those patterns? would it make sense to shuffle the column vectors resulting from im2col to control these patterns?\n* In the context of compression, many other methods exist but they're not shown in the paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "limitations are not discussed in depth", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "3S_J8znhfwZ", "reviewer": "Reviewer_fZAT", "summary": "In this work, the authors propose a new way named deformable butterfly (DeBut) to represent the linear transformation between feature layers in a deep neural network. It is based on a chain of butterfly factor matrices that can be used together to form a densified matrix for linear transformation. The experiments show the proposed method can reduce the model size while maintaining similar test accuracy.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Compared to the prior work [5,6], there is an extension from square matrix to non-square matrix for linear transformation.\n- The runtime complexity can be lower than O(nlogn).\n- The number of parameters can be reduced.\n- The idea of DeBut looks quite novel to me.\n- The paper is well-written and the complicated idea is well illustrated with figures and explanations.\n\nWeaknesses:\n- It seems that the accuracy may drop a little bit with DeBut, although the model size is reduced. In Table 4, the Top-1 accuracy is lower than ResNet-50.\n- Is there any example to demonstrate the difference DeBut-mono and DeBut-bulging? I am confused by these two designs. Why the authors propose these two designs and what are the pros and cons?\n- Are the results shown in the experiments by training a model with DeBut from scratch (or fine-tuning) or approximating a pre-trained model with DeBut?\n- Why DeBut does not improve the model accuracy, compared to Conv and FC?\n- It seems the model with DeBut runs slower than the baseline (e.g., ResNet50)?\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations should be better explained, and I do not see negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0ox8CpUpC5R", "reviewer": "Reviewer_8jnC", "summary": "The authors propose “deformable butterfly”, a variant of the butterfly transform that does not require power-of-two size butterfly factor matrices. The authors show how to adapt pre-trained models to use DeBut in place of convolution and fully-connected layers and also show experiments training models with DeBut chains from scratch. The authors provide experiments on a range of CNN architectures and datasets and compare to existing transforms like Adaptive Fastfood and Butterfly.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and organized. I found the work very interesting, but my main concerns are novelty and unique contribution over existing work. As I understand it, the primary contribution in methodology is that DeBut breaks the power-of-two (POT) constraint required in standard Butterfly matrices. This is certainly practically useful, but I don’t think this change is novel enough to merit publication for this contribution alone. Additional contributions like empirical gains over Butterfly matrices would’ve helped, but the advantage over Butterfly matrices seems to be marginal. Both techniques still do not appear to be simple substitutes for existing layers without accuracy loss. For example, 0.65% accuracy drop (almost 2x increase in error) training from scratch when replacing 3 out of 5 layers in LeNet and 1.5% decrease in top-1 accuracy using ALS with ResNet-50 with DeBut applied to only 9 layers in the model.\n\nComments\n1. Some of the language in this work is very sensational. For example, “renders a new paradigm for network compression”.\n2. In practice, convolution is rarely implemented with im2col + GEMM because of the memory bandwidth cost and memory footprint of the im2col. Modern high-performance convolutions fuse the im2col + GEMM into a single kernel with clever indexing (called an “implicit-GEMM” convolution, as opposed to “explicit-GEMM” where im2col is used).\n3. The authors should include the baseline accuracy in their result tables to make it easier for the reader.\n4. I don’t see how DeBut “unif[ies] and homogenize[s]” convolution and FC layers more than they already are. DeBut using an im2col transform and then approximating the GEMM portion of the convolution is just exploiting what was already known.\n5. The statement “where other fast linear transform schemes fail” is an exaggeration. The empirical gains over Butterfly appear to be limited and Adaptive FastFood produces much better theoretical efficiency (although it appears to be expensive in practice).\n6. I’d like to see more details on the implementations benchmarked in Table 6. Given all techniques listed are not mainstream I doubt the implementations are highly optimized and I’d like to understand how much this contributes to the performance discrepancies. For example, I’m not sure why DeBut would be much faster than Butterfly given they are essentially the same computation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not identify potential negative societal impacts in this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I did not identify ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2hrs"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Congratulations, the paper is accepted to NeurIPS 2021!
Please incorporate the edits and corrections as discussed in the rebuttal and reviews. 
Furthermore, tone down the "sensational" language used in the work; try to keep language as factual as possible. 
Decision: Accept (Poster)