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": "wNoVlj3h_Y2", "reviewer": "Reviewer_X4Ja", "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.", "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": "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.\n\nUsage 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.\n\nWhile 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?\n\nLines 130-131: Comparing GEMM with sparse matrix multiplication may be incorrect and is highly dependent on the hardware.\n\nThe 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?\n\nLine 200: Are the learned parameters of biases and BatchNorms accounted for in the model compression ratio?\n\nWhy are results for \"w/o ALS\" not reported in Tables 3 and 4? \n\nThe lack of per-layer chain automation and experiments which exclude more than one layer are the biggest concerns. \n\nOther questions/comments:\n- Fig.2 looks cluttered\n- Line 104: discussion of circulant structure at the beginning of the main method section is misplaced, as it sidetracks from understanding the proposed method.\n- Tables might not be the best way to show the performance/compression trade-off; please consider adding plot(s). \n- 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.\n- suggestion: a syllable-based abbreviation of the method may have negative connotations\n- suggestion: \"bulging\" -> \"concave\"\n- suggestion: \"bipolar test\" -> \"information flow test\". e.g. could be conducted with {0,1} - not bipolar anymore.  \n\nReferences:\n\n- [1] Garipov et.al: Ultimate tensorization: compressing convolutional and FC layers alike\n- [2] Wang et.al: Wide Compression: Tensor Ring Nets\n\n============== Post-rebuttal comment\n\nAfter 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.\n\nPS: 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitation as mostly addressed, see general comments.\n\nSocietal impact N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Yr586l8Ujc_", "reviewer": "Reviewer_jjhd", "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.", "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": "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.\n\nThe DeBut factor designing seems ad-hoc to me. Is there a way to automatically get the chain definition given input/output shape?\n\nAlthough 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).\n\nIt is not novel and not a unique DeBut attribute to unify conv and FC layer as matrix multiplication.\n \nOverall 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.\n\n[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.\n\n===========Post-rebuttal comment\n\nThanks 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think this paper has potential negative societal impact. For the limitations please see above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "AEtUh0d-AsD", "reviewer": "Reviewer_tsAg", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 proposed DeBut has some good properties, but there are some problems in the work as follows:\n- 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.\n- There is no experiment to demonstrate the lightweight and low inference complexity comparing to the exiting butterfly-based methods.\n- 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.\n- 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.\n- 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. It is encouraged to discuss the limitation unsolved in the paper.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1YkydUkMDG3", "reviewer": "Reviewer_tNGs", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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:\n1. The paper is well-written and easy to understand. Section 3 provides valuable intuition, and I enjoyed reading it.\n2. The method can significantly reduce the number of parameters and computation in fully-connected and conv layers.\n3. The method is novel to the best of my knowledge.\n4. The alternating least squares initialization for DeBut factors is clever and seems to work well.\n\nWeaknesses:\n1. 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.\n\nQuestions & comments:\n1. Why is the method called \"deformable\" butterfly?\n2. 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?\n$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.\n3. Page 5, line 134: I can't find the densification condition in Appendix I. Are there more general densification conditions?\n4. 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?\n5. 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?\nI wonder if you can iteratively adjust the shape of the factors and do ALS at the same time to find the best approximation.\n6. 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?\n7. 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.\n\n============== Post-rebuttal\n\nThank you for the detailed response to my questions. That has helped me understand the proposed method better. \n\nI'm keeping my rating and still recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)