Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practice
Authors: Nir Ailon
Omer Leibovitch
Vineet Sreedharan Nair
Venue:  (2021)
Keywords: Butterfly Network
Matrix approximation
Encoder-Decoder Network
Optimization Landscape

Abstract: A butterfly network consists of logarithmically many layers, each with a linear number of non-zero weights (pre-specified). The fast Johnson-Lindenstrauss transform (FJLT) can be represented as a butterfly network followed by a random projection to a subset of the coordinates. Moreover, a random matrix based on FJLT with high probability approximates the action of any matrix on a vector. Motivated by these facts, we propose to replace a dense linear layer in any neural network by an architecture based on the butterfly network. The proposed architecture significantly improves upon the quadratic number of weights required in a standard dense layer to nearly linear with little compromise in expressibility of the resulting operator. In a collection of wide variety of experiments, including supervised prediction on both the NLP and vision data, we show that this not only produces results that match and often outperform existing well-known architectures, but it also offers faster training and prediction in deployment. To understand the optimization problems posed by neural networks with a butterfly network, we study the optimization landscape of the encoder-decoder network, where the encoder is replaced by a butterfly network followed by a dense linear layer in smaller dimension. Theoretical result presented in the paper explain why the training speed and outcome are not compromised by our proposed approach. Empirically we demonstrate that the network performs as well as the encoder-decoder network.

Under review as a conference paper at ICLR 2021
SPARSE LINEAR NETWORKS WITH A FIXED BUTTER- FLY STRUCTURE: THEORY AND PRACTICE
Anonymous authors Paper under double-blind review
ABSTRACT
A butterfly network consists of logarithmically many layers, each with a lin- ear number of non-zero weights ppre-specified). The fast Sahnson-Lindenstrauss transform (FJLT) can be represented as butterfly network followed by a projec- tion onto random subset of the coordinates. Moreover, random matrix based on FJLT with high probability approximates the action of any matrix on vec- tor. Motivated by these facts, we propose to replace a dense linear layer in any neural network by architecture based on the butterfly network. The proposed architecture significantly improves upon the quadratic number of weights required in standard dense layer nearly linear with little compromise in expressibility of the resulting operator. In a collection of wide variety of experiments, includ- ing supervised prediction not only produces results that match and often outperform existing well-known architectures. but also offers faster training and prediction deployment. To understand the optimization problems posed by neural networks with butterfly network, we study the optimization landscape of the encoder-decoder network, where the encoder is replaced by a butterfly network followed by dense linear layer smaller dimension. Theoretical result presented in the paper explain why the training speed and outcome are not compromised by our proposed approach. Empirically we demonstrate that the network performs as well as the encoder- decoder network.
both the NLP and vision data, we show that this
INTRODUCTION
A butterfly network (see Figure Appendix[A] is layered graph connecting a layer of inputs to a layer of n outputs with O(log n) layers, where each layer contains 2n edges. The edges connecting adjacent layers are organized in disjoint gadgets, each gadget connecting pair of nodes in one layer with a corresponding pair in the next layer by a complete graph. The distance between pairs doubles from layer to layer. This network structure represents the execution graph of the Fast Fourier Trans- form (FFT) (Cooley and Tukey| 1965), Walsh-Hadamarr transform, and many important transforms in signal processing that known to have fast algorithms to compute matrix-vector products.
Ailon and Chazelle (2099) showed how to use the Fourier (or Hadamard) transform to perform fast Euclidean dimensionality reduction with JJhnsso and Lindenstrauss (1984) guarantees. The resulting transformation, called Fast Johnson Lindenstrauss Transform (FJLT), was improved in subsequent works (Ailon and Liberty) 2009. Krahmer and Ward 201T). The common theme in this line of work is to define a fast randomized linear transformation that is composed of a random diagonal matrix, followed by a dense orthogonal transformation which can be represented via butterfly network, followed by a random projection onto subset of the coordinates (this research is still active, see e.g. Jaain al. (2000). particular, an FJLT matrix can be represented (explicitly) by butterfly network followed by projection onto random subset of coordinates (a truncation operator). We refer to such a representation as a truncated butterfly network (see Section
like arguments show that with high probability for any W E R and any x E R Wx is close to (J J2) J1)x where J1 E R Xp1 and Jz E X both FJLT, and k log n1, A/ log n2 (see Section 4.2 for details). Motivated by this, propose to replace a dense (fully-connected) linear layer of size na X n, in any neural network by the following architecture: Jf J2,, where J1, Jz be represented by truncated butterfly
Simple

---

Under review as a conference paper at ICLR 2021
network and W is a 22 x l1 dense linear layer. The clear advantages of such strategy are: (1) almost all choices of the weights from a specific distribution, namely the one mimicking FJLT, preserve accuracy while reducing the number of parameters, and (2) the number of weights is nearly linear in the layer width of W (the original matrix). Our empirical results demonstrate that this offers faster training and prediction in deployment while producing results that match and often outperform existing known architectures. Compressing neural networks by replacing linear layers with structured linear transforms that are expressed by fewer parameters have been studied extensively in the recent past. We compare our approach with these related works in Section
Since the butterfly structure adds logarithmic depth to the architecture, it might pose optimization related issues. Moreover, the sparse structure of the matrices connecting the layers in a butterfly network defies the general theoretical analysis of convergence of deep linear networks. We take a small step towards understanding these issues by studying the optimization landscape of a encoder-decoder network (two layer linear neural network), where the encoder layer is replaced by a truncated butterfly network followed by a dense linear layer in fewer parameters. This replacement is motivated by the result of (aarlos 2006), related to fast randomized low-rank approximation of matrices using FJLT (see Section 4.2 for details). We consider this replacement instead of the architecture consisting of two butterfly networks and dense linear layer as proposed earlier, because is easier to analyze theoretically. We also empirically demonstrate that our new network with fewer parameters performs as well as an encoder-decoder network.
The encoder-decoder network computes the best low-rank approximation of the input matrix. is well-known that with high probability a close to optimal low-rank approximation of a matrix obtained by either pre-processing the matrix with an FJLT (Sarlós) 2006) or random sparse matrix structured as given in Clarkson and Woodruff (2009) and then computing the best low-rank approximation from the rows of the resulting matrix A recent work by Indyk et al. (2199) studies this problem in the supervised setting, where they find the best pre-processing matrix structured as given in Clarkson and Woodruff (2009) from a sample of matrices (instead of using a random sparse matrix). Since an FJLT can be represented by a truncated butterfly network, we emulate the setting of Indyk et al. 2019) but learn the pre-processing matrix structured as a truncated butterfly network.
2 OUR CONTRIBUTION AND POTENTIAL IMPACT
We provide an empirical report, together with a theoretical analysis to justify our main idea of using sparse linear layers with a fixed butterfly network in deep learning. Our findings indicate that this approach, which is well rooted in the theory of matrix approximation and optimization, can offer significant speedup and energy saving in deep learning applications. Additionally, we believe that this work would encourage more experiments and theoretical analysis to better understand the optimization and generalization of our proposed architecture (see Future Work section).
On the empirical side- The outcomes the following experiments are reported:
(1) In Section 6.1 we replace dense linear layer in the standard state-of-the-art networks, for both image and language data, with an architecture that constitutes the composition of (a) truncated butterfly network, (b) dense linear layer in smaller dimension, and (c) transposed truncated butterfly network (see Section 4.2). The structure parameters are chosen so as to keep the number of weights near linear (instead of quadratic).
(2) In Sections 6.2 and 6.3 we train a linear encoder-decoder network in which the encoder is replaced by truncated butterfly network followed by dense linear layer in smaller dimension. These experiments support our theoretical result. The network structure parameters are chosen so keep the number of weights in the (replaced) encoder near linear in the input dimension. Our results (also theoretically) demonstrate that this has little to no effect on the performance compared to the standard encoder-decoder network.
we learn the best pre-processing matrix structured as a truncated butterfly network (3) In Section 7
to perform low-rank matrix approximation from given sample of matrices. We compare our results
'The procpsiss matrix is multiplied from the left.
2

---

Under review as a conference paper at ICLR 2021
to that of Indyk al. (2019). which learn the pre-processing matrix structured given in Clarkson and Woodruff (2009).
On the theoretical side The optimization landscape of linear neural networks with dense matrices have been studied by [Baldi and Hornik (189), and Kawaguchi (2016). The theoretical part of this work studies the optimization landscape of the linear encoder-decoder network in which the encoder is replaced by a truncated butterfly network followed by a dense linear layer in smaller dimension. We call such a network as the encoder-decoder butterfly network. We give an overview of our main result, Theorem [| here. Let X E Innd and Y E R be the data and output matrices respectively. Then the encoder-decoder butterfly network is given as Y DEBX, where D E I x and E' E R&x are dense layers, B is an f x n truncated butterfly network (product of log n sparse matrices) and h S m =n n. (see Section [}. The objective is to learn D, E and B that minimizes ||Y YI.. Theorem 1 shows how the loss at the critical points of such a network depends on the eigenvalues of the matrix Σ - YX" "Xx"B((XX" (BXX* 1" - comparison, the loss at the critical points of the encoder-decoder network (without the butterfly network) depends on the eigenvalues of the matrix E' = -X"" xY" (Baldi and Homni 1989 In particular, the loss depends on how the learned matrix B changes the eigenvalues of > we learn only for an optimal D and E, keeping B fixed (as done in the experiment in Section 6.3 then it follows from Theorem || that every local minima is a global minima and that the loss at the local/global minima depends on how B changes the top k eigenvalues of h". This inference together with a result by |aalós (2006) is used to give a worst-case guarantee in the special case when Y = X (called auto-encoders that capture PCA; see the below Theorem
In
3 RELATED WORK
Important transforms like discrete Fourier, discrete cosine, Hadamard and many more satisfy a prop- erty called complementary low-rank property, recently defined by [i et al. (2015). For an n X n ma- trix satisfying this property related to approximation of specific sub-matrices by low-rank matrices, Michielssen and Boag (199)) and OndDOeNell al. (2010) developed the butterfly algorithm to compute the product of such a matrix with vector in O log n) time. The butterfly algorithm factorizes such a matrix into Ollo n) many matrices, each with (n) sparsity. In general, the butterfly algorithm has pre-computation stage which requires Onn²) time (O OO'Neil et al. 2010 Seljebotn| 2012). With the objective of reducing the pre-computation cost Li et al. (2015); Li and Yang (2017) compute the butterfly factorization for an
matrix satisfying the complementary low-rank property in O(n)) time. This line of work does not learn butterfly representations for matrices apply it in neural networks, and is incomparable to our work.
A few works in the past have used deep learning models with structured matrices (as hidden layers). Such structured matrices can be described using fewer parameters compared to a dense matrix, and hence representation can be learned by optimizing over a fewer number of parameters. Examples of structured matrices used include low-rank matrices (Denil et al. 2013 Sainath et al., 2013).
circulant matrices (Cheng al., 2013 Ding et al. 2017). low- distorrtn projections (Yang et al. 2015), Toeplitz like matrices (Sindhwani et al. 2015 Lu et al. 2016 Ye et al. [2018). Fourier-relater
transforms (Moczulski et al., (016) and matrices with low-displacement rank (Thomas et all 2018
Recently Alizadeh et al. (2020) demonstrated the benefits of replacing the pointwise convolutional layer in CNN's s by a butterfly network. Other works by Mocanu et al. (208)) et al. (2019): Wang
et al. (2020); Verdenius et al. (2020) consider different approach to sparsify neural networks. The
works closest to ours are by] Yang et al. (2015). Moczulski et al. (0016), and [ao et al. 2020 and make comparison below.
Yang et al. (2015) and Moczulski et al. (2016) attempt to replace dense linear layers with a stack of structured matrices, including butterfly structure (the Hadamard or the Cosine transform), but they do not place trainable weights on the edges of the butterfly structure as we do. Note that adding these trainable weights does not compromise the run time benefits in prediction, while adding to the expressiveness of the network in our case. Dao et al. (2020) replace handcrafted structured sub- networks in machine learning models by a kaleidoscope layer, which consists of compositions of butterfly matrices. This is motivated by the fact that the kaleidoscope hierarchy captures a structured matrix exactly and optimally in terms of multiplication operations required to perform the matrix
At a critical point the gradient of the loss function with respect the parameters in the network is zero
3

---

Under review as a conference paper at ICLR 2021
vector product operation. Their work differs from we propose replace any dense linear layer in a neural network (instead of a structured net-oe) by the architecture proposed in Section 4.2 Our approach is motivated by theoretical results which establish that this can be done with almost no loss in representation.
Finally, Dao et al. (2019) show that butterfly representations of standard transformations like discrete Fourier, discrete cosine, Hadamard mentioned above can be learnt efficiently. They additionally show the following: a) for the benchmark task of compressing single hidden layer model they compare the network constituting of a composition of butterfly networks with the classification accuracy of a fully-connected linear layer and b) in ResNet a butterfly sub-network added to get an improved result. In comparison, our approach to replace a dense linear layer by the proposed architecture in Section 4.2 motivated by well-known theoretical results as mentioned previously, and the results of the comprehensive list of experiments in Section 6.1 support our proposed method.
PROPOSED REPLACEMENT FOR A DENSE LINEAR LAYER
In Section 4. we define truncated butterfly network, and in Section 4.2 we motivate and state our proposed architecture based on truncated butterfly network to replace a dense linear layer in any neural network. All logarithms are in base 2, and [n]] denotes the set (I....,n).
4.1 TRUNCATED BUTTERFLY NETWORK
Definition 4.1 (Butterfly Network). Let n be an integral power of Then an n X butterfly network B (see Figure 6 is a stack of of log n linear layers, where in each layer i {0. ..... logn 1}. bipartite clique connects between pairs of nodes J1.J2 E [m]. for which the binary representation of -1 1 and j2 differs only in the i i'th bit. In particular, the number of edges in each layer is 2n.
In what follows, truncated butterfly network is butterfly network in which the deepest layer is truncated, namely, only a subset of neurons are kept and the remaining n E are discarded. The in- teger é is tunable parameter, and the choice of neurons is always assumed to be sampled uniformly at random and fixed throughout training in what follows. The effective number of parameters (train- able weights) in a truncated butterfly network is most 2n log é + 6n, for any l and any choice of neurons selected from the last layer We include a proof of this simple upper bound in Appendix for lack of space (also, refer to Ailon and Liberty (2009) for a similar result related to computation time of truncated FFT). The reason for studying truncated butterfly network follows (for exam- ple) from the works (Ailon and Chazelle, 2009 Ailon and Liberty 2009 Krahmer and Ward [01 These papers define randomized linear transformations with the Johnson- Lindonns-anddssrssss property and an efficient computational graph which essentially defines the truncated butterfly network. In what follows, we will collectively denote these constructions by FJLT.
4.2 MATRIX APPROXIMATION USING BUTTERFLY Y NETWORKS
We begin with the following proposition, following known results matrix approximation (proof in Appendix B
Proposition 1. Suppose J1 E R x and J2 E R are matrices sampled from FJLT distribu- tion, and let W E R222"11 Then for the random matrix W (Jī J2) (JT J1), any unit vector (0.0minnn1..)))
E T and any E (0, 1). Pr [||' Wx| S <|II 2
From Proposition D follows that W approximates the action of W with high probability on any given input vector. Now observe that W" is equal to J J1, where W J,W Since J/ and J2 are FJLT, they can be represented by a truncated butterfly network, and hence it is conceivable to replace a dense linear layer connecting nn neurons to n2 neurons (containing n n2 variables) in any
NNoe that if is not power of 2 then we work with the first columns of the E n' truncated butterfly network, where n' the closest number to that is greater than and is a power of
'To be precise, the construction in Ailon and Chazelle (2009) Ailon and Liberty 22009) and Krahmer and Ward (20TT) also uses random diagonal matrix, but the values of the diagonal entries can be 'absorbed' inside the weights of the first layer of the hutterfly network.
4

---

Under review as a conference paper at ICLR 2021
neural network with composition of three gadgets: a truncated butterfly network of size k X fl,, followed by dense linear layer of size k2 x k1, followed by the transpose of a truncated butterfly network of size 2 x n2. In Section 6.1] replace dense linear layers in common deep learning networks with our proposed architecture, where we set l = log ni and 22 = 1o..2- 122-
5 ENCODER-DECODER BUTTERFLY NETWORK
Let X E RT and Y E R be data and output matrices respectively, and S m S Then the encoder-decoder network for X is given as
==DEX
where E E Rexn, and D Ik=* are called the encoder and decoder matrices respectively. For the special case when Y = X. is called auto-encoders. The optimization problem is to learn matrices D and E such that | - Y is minimized. The optimal solution is denoted as Y* D and E In the case of nuto-encoders X = Xy. where X₂ is the best rank A approximation of X. In this section, we study the optimization landscape the encoder-decoder butterfly network: an encoder-decoder network, where the encoder is replaced by truncated butterfly network followed by dense linear layer in smaller dimension. Such a replacement motivated by the following result from Sarlós (2006), in which A& = =||x I
Let X Raxd, Then with probability least 1/2, the best rank k approximation of X from the rows of JX (denoted Jx((X),. where is sampled from an & x n. FJLT distribution and é
Proposition 2.
(k log + k/e) satisfies (X)+ XIi - +1+e)
Proposition 2 suggests that in the case of auto-encoders we could replace the encoder with trun- cated butterfly network of size l x n followed by dense linear layer of size k x l, and obtain network with fewer parameters but loose very little in terms of representation. Hence, it is worth- while investigating the representational power of the encoder-decoder butterfly network
== DEBX.
Here, X, and D are as in the encoder-decoder network, E R is a dense matrix, and B an é x n truncated butterffy network. In the encoder-decoder butterfly network the encoding is done using EB, and decoding done using D. This reduces the number of parameters matrix from kn (as in the encoder-decoder network) to kt + Onn log E). Again the objective is to learn matrices D and E, and the truncated butterfly network B such that ||Y YIE The optimal solution is denoted as Y*, D", E", and B" Theorem shows that the loss at a critical point of such network depends the cigenvalues of EBB YX ( x BT)) "XYY.. when X B" is invertible and EB) has distinct positive eigenvalues. The loss defined as || - -
the encoding
T is minimized.
Theorem 1. Let D, E and be a point of the encoder-decoder network with a truncated butterfly network satisfying the following: a) BX B" is invertible, b) (B) has & distinct positive eigen- values A1 >
> dt. and c) the gradient of L(Y) with respect to the parameters in D and E matrix is zero. Then corresponding to this point (and hence corresponding to every critical point) there is an I C [4] such that L(Y) at this point is equal to tr(YY")- -Eir X Moreover if the point is local minima then 1 [k].
The proof of Theorem is given in Appendix C We also compare our result with that of Baldi and Hornik 1989) and Kawaguchi (2016), which study the optimization landscape of dense linear neural networks in Appendix [C] From Theorem[]] [ follows that is fixed and only D and E are trained then local minima is indeed global minima. We use this to claim worst-case guarantee using a two-phase learning approach to train an auto-encoder.
this case the optimal solution is denoted as (Y), Dg, and Eg. Observe that when Y x, B (X) is the best rank & approximation of X computed from the rows of B.X.
Two phase learning for auto-encoder: Let l = & log & + k/e and consider two phase learning strategy for auto-encoders, as follows: In phase one B is sampled from an EJLT distribution, and then only D and E are trained keeping B fixed. Suppose the algorithm learns D' and E' at the end
Possibly multiple 1" and E* exist such that Y D" X.
5

---

Under review as a conference paper at ICLR 2021
Daiseet Name
Tosk
Model
Cifar-i Kibal-ikKiblllvsyy Krillevkk
2112
Image clacsification
EfficienNee
2019
Citar-10 Knniews
2014
Image clacsitication
PreActResNorz
Ciar-100 100 Krohiesk
211
Image cheeofication
scresnet
152
Pirelai
Imspelet Danr of
Image clacaification
senet1 Hird
3121
CoNLL-03 Tivez
Mer 2001
Named Entily Recegnitsn (English)
Seqpence Tagyer
ALNK
2010
CONEU10X Freg Kin Sing 2ma Manqur
Namal Faiity Recogrition (German)
Flairs Sequence Tagger
AINE
ATX
271
Pone Teigiat Marcis of
1994
Part-of-Specch Tigging
Flair's Sequence Tiggo
201
AKIR 2
4019
Table I:
Data and the corresponding architectures used in the fast matrix multiplication using but- terfly matrices experiments.
of phase one, and X" = D'E"B. Then Theorem | guarantees that, assuming E(B) has & distinct E'
positive eigenvalues and E' are a local minima, D' DB. E' = Eg. and X' = Bx(X) Namely X' is the best rank k approximation of X from the rows of BX. From Proposition with probability at least 2. L(X') < (1 +) In the second phase all three matrices are trained to improve the loss. In Sections 6.2 and 6.3 we train encoder-decoder butterfly network using the standard gradient descent method. In these experiments the truncated butterfly network is initialized by sampling it from an FJLT distribution, and D and E are initialized randomly as Pytorch.
EXPERIMENTS ON DENSE LAYER REPLACEMENT AND -DECODER BUTTERFLY NETWORK
In this section we report the experimental results based on the ideas presented in Sections
4.2 and
6.1 REPLACING DENSE LINEAR LAYERS BY THE PROPOSED ARCHITECTURE
This experiment replaces a dense linear laver of size n2 X Ri in common deep learning architectures with the network proposed in Section 4.2 6 The truncated butterfly networks are initialized by sam- pling it from the FJLT distribution, and the dense matrices are initialized randomly in Pytorch. We set k, = log n and 2n = log n2. The datasets and the corresponding architectures considered summarized in Table 1 For each dataset and model, the objective function is the same as de- fined in the model, and the generalization and convergence speed between the original model and the modified one (called the butterfly model for convenience) are compared. Figure 7 in Appendix r.prrtts the number of parameters in the dense linear layer of the original model, and in the replaced network, and Figure 8 Appendix [D.T displays the number of parameter in the original model and the butterfly model. In particular, Figure 7 shows the significant reduction in the number of parameters obtained by the proposed replacement. On the left of Figure [ the test accuracy of the original model and the butterfly model is reported, where the black vertical lines denote the error bars corresponding to standard deviation, and the values above the rectangles denote the average accuracy. On the right of Figure [eguure[oberre observe that the test accuracy for the butterfly model trained with stochastic gradient descent is even better than the original model trained with Adam in the first few epochs. Figure 12 in Appendix App compares the test accuracy in the the first 20 epochs of the orig- inal and butterfly model. The results for the NL.P tasks in the interest of space are reported in Figure g Appendix [D. The training and inference times required for the original model and the butterfly model in each of these experiments are reported in Figures I0 and I1 in Appendix D.I We remark that the modified architecture also trained for fewer epochs. architecture does better than the normal architecture, both in the rate of convergence and in the final accuracy/F1 score. Moreover, the training time for the modified architecture is less.
almost all the cases the modified
6.2 ENCODER-DECODER BUTTERFLY NETWORK WITH SYNTHETIC GAUSSIAN AND REAL DATA
This experiment tests whether gradient descent based techniques can be used to train encoder- decoder butterfly network. In all the experiments in this section Y = X. Five types of data matrices are tested, whose attributes are specified in Table 2 Two among them are random and
II all the architectures considered the final linear layer before the output layer is replaced, and n; and n2 depend on the architecture.
In 2 HS-SOD denotes dataset for hyperspectral images from natural scenes Imaamgluu et al. 2018

---

Under review as a conference paper at ICLR 2021
T:st 300-000
Normal (SG3)
12
(Adam)
(Adam)
0.00
0.25
0.50
0.75
100 Epach
125
1.5
1.75
2.00
Figure 1: Left: comparison of final test accuracy with different image classification models and data sets; Right: comparison of test accuracy in the first few epochs with different models and optimizers on CIFAR-10 with Pre1ctResNet18
three are constructed using standard public real image datasets. In the interest of space, the con- struction of the data matrices is explained in Appendix D.2 For the matrices constructed from the image datasets, the input coordinates randomly permuted, which ensures the network cannot take advantage of the spatial structure in data. For each of the data matrices the loss obtained via training the truncated butterfly network with the Adam optimizer is compared to Aạ (denoted as PCA) and (X)) - X where J is an x n matrix sampled from the FJLT distribution (denoted FJLT+PCA). Figure2repont reports the loss Gaussian 1 and MNIST, whereas Figure 13 in Appendix D.2 reports the loss for the remaining data matrices. Ohserve that for all values of the loss for the encoder-decoder butterfly network is almost equal Ag. and in fact Aạ for small and large values of k.
Name
11
rank
Gaussian 1
1024
1024
32
Gaussian 2
1024
1024
64
MNIST
1024
1024
1024
Olivetti
1024
4096
1024
HS-SOD
1024
768
768
Table 2: Data used in the truncated butterfly auto-encoder reconstruction experiments
1000
FLT + PCA
1000
FLT + PCA
Truncated butterfly autoencoder
Truncated butterfly autoencoder
800
600
Approciaation
800
400
Figure 2: Approximation еπоо on data matrix with various methods for various values of k. Left: Gaussian 1 data, Right: MNIST data
6.3 TWO-PHASE LEARNING FOR ENCODER-DECODER BUTTERFLY NETWORK
This experiment is similar to the experiment in Section 6.2 but the training in this case is done in two phases. In the first phase, B is fixed and the network trained to determine an optimal D and E. In the second phase, the optimal D and E. determined in phase used the initialization, and the

---

Under review as a conference paper at ICLR 2021
network is trained over D, E and B to minimize the loss. Theorem ensures worst-case guarantees for this two phase training (see below the theorem). Figure reports the approximation error of an image from Imagenet. The red and green lines in Figure correspond the approximation error the end of phase one and two respectively.
800
30.0
Appeodrration
trancated butterfly aatnencoder
Random truncated butterly autemncader
Optimal int truncated butterlyy sulzencader
200
truncated autoencoder butteftyy
20
00
130
120
20.0
22.5
25.0
30.0
32.5
35.0
375
Figure 3: Approximation error achieved by different methods and the same zoomed on in the right
SKETCHING ALGORITHM FOR LOW-RANK MATRIX DECOMPOSITION PROBLEM USING BUTTERFLY NETWORK
The recent influential work by Indyk et al. 2019) considers supervised learning approach to com- pute an f X pre-conditioning matrix B for low-rank approximation of n d matrices. The matrix B has fixed sparse structure as in Clarkson and Woodrufi (2009), each column as non-zero entry (chosen randomly) which are learned to minimize the loss over training set of matrices. In this section, present experiments with the setting being similar to that in Indyk al. (2019), except that B is now represented as an X п truncated butterfly network. Our setting is similar to that in Indyk et al. (2019), except that B is now represented experiments suggests that indeed learned truncated butterfly network does better than a random matrix, and even learned as in Indyk et (2019).
x truncated butterfly network. Our
Setup:
Suppose XI...., X₁ R are training matrices sampled from distribution D. Then
B is computed that minimizes the following empirical loss: Eieta || B& (X. We compute (X,) using truncated SVD of BX; (as in Algorithm 1, Indyk et al. (019H) Similar to Indyk et al. (219). the matrix B is learned by the baok-propngation algorithm that uses differentiable SVD implementation to calculate the gradients, followed by optimization with Adam such that the butterfly structure of B is maintained. The learned B can be used the pre-processing matrix for any matrix in the future. The test error for a matrix B and a test set Te is defined as follows:
EITTe (B) = Ex-Te [||X B&
ApPTe where ApPTe = Ex [[XX - X 11
Experiments and Results: The experiments performed the datasets shown in Table 3 In HS-SOD Imamoglu et al. (2018) and 1rizhe-O0 (2012) 400 training matrices (1 400). and 100 test matrices matrices are sampled. In Tech Davido et al. (2004) each matrix has 835,422 rows but on average only 25,389 rows and 195 columns contain non-zero entries. For the in each dataset, the coordinates of each row are randomly permuted. Some of the matrices in the datasets have much larger singular values than the others, and to avoid imbalance in the dataset, the matrices are normalized so that their top singular values are all equal, as done in Indyk et al. 2019). For each of the datasets, the test error for the learned B via our truncated butterfly structure
sampled, while in Tech 200 training matrices
200), and 95 test
reason in Section 6.2
Name HS-SOD
n
d
1024
768
CIFAR-10
32
32
Tech
25,389
195
Table Data used Sketching algorithm for low-rank matrix decomposition experiments.
8

---

Under review as a conference paper at ICLR 2021
compared to the test errors for the following three cases: 1) B is learned sparse sketching matrix as in Indyk et al. (2019), b) B is a random sketching matrix as in Clarkson and Woodruff 2009), and c) B Is L x Gaussian matrix. Figure 4 compares the test enror for E = 20, and TO, where AppTe = 10.56. Figure 14 in Appendix compares the test emoos of the different methods in the extreme
Appendix H compares the test errors of the different methods for various values of L. Table 4 in Appendix B in Appendix reports the test error for different values of f and k. Figure 16 in in Appendix
when k 1, and Figure 15
[ shows the test error for L 20 and k 10 during the training phase on HS-SOD. In Figure 16 it is observed that the butterfly learned able to surpass sparse learned after a merely few iterations.
Figure 6 compares the test eπrоr for the learned B via our truncated butterfly structure to learned matrix B with N non-zero entries in each column - the N non-7ero location for each column are chosen uniformly at random. The reported test errors are on HS-SOD, when e = 20 and k = 10. Interestingly, the error for butterfly learned not only less than the error for sparse learned (N as in [Indyk et al. 2019)) but also less than than the enror for dense learned (N 20). In particular, our results indicate that using a learned butterfly sketch can significantly reduce the approximation loss compared to using learned sparse sketching matrix.
24-
2:14
Fperss Dandtn
Seaert Dncned
Figure 5: Test errors for various values of N and a learned butterfly matrix
Figure 4: Test error by different sketching matrices different data sets
8 DISCUSSION AND FUTURE WORK
Among other things, this work showed that it is beneficial replace dense linear layer in deep learning architectures with more compact architecture (in terms of number of parameters), using truncated butterfly networks. This approach justified using ideas from efficient matrix ap- proximation theory from the last two decades. however, results in additional logarithmic depth to the network. This issue raises the question of whether the extra depth may harm convergence of gradient descent optimization. To start answering this question, show, both empirically and theoretically, that in linear encoder-decoder networks in which the encoding is done using a butterfly network, this typically does not happen. To further demonstrate the utility of truncated butterfly networks, consider a supervised learning approach as in [Indyk et al. (2019), where we learn how to derive low rank approximations of a distribution of matrices by multiplying pre-processing linear operator represented as butterfly network, with weights trained using a sample of the distribution.
Discussion:
The main open questions arising from the work related to better understanding the optimization landscape of butterfly networks. The current tools for analysis of deep linear networks do not apply for these structures, and more theory necessary. would be interesting determine whether replacing dense linear layers in any network. with butterfly networks as in Section 4.2 harms the convergence of the original matrix. Another direction would be check empirically whether adding non-linear gates between the layers (logarithmically many) of butterfly network improves the performance of the network. In the experiments in Section we have replaced a single dense layer by our proposed architecture. It would be worthwhile to check whether replacing multiple dense linear layers in the different architectures harms the final accuracy. Similarly, it might be insightful to replace convolutional layer by architecture based truncated butterfly network. Finally, since our proposed replacement reduces the number of parameters in the network, it might be possible to empirically show that the new network is more resilient over-fitting.
Future Work:

---

Under review as a conference paper at ICLR 2021
ACKNOWLEDGEMENT
This project has received funding from European Union's Horizon 2020 research and innovation program under grant agreement No 682203 -ERC-[ Inf-Speed-Tradeefff.
REFERENCES
N. Ailon and B. Chazelle. The fast joonson-lindensrrann transform and approximate nearest neigh- bors. SIAM J. Comput.. 39(1):022-32 2009.
N. Ailon and E. Liberty. Fast dimension reduction using rademacher series dual BCH codes. Discret. Comput, Geom., 42(4))615-630, 2009.
A. Akbik, Blythe, and R. Vollgraf. Contextual string embeddings for sequence labeling. In COLING 2018, 27th International Conference Computational Linguistics, pages 1638-1649, 2018.
A. Akbik, T. Bergmann, and R. Vollgraf. Pooled contextualized embeddings for named entity recog- nition. In NAACL 2019, 2019 Annual Conference of the North American Chapter of the Associa- tion for Computational Linguistics, page 724-728, 2019.
K. Alizadeh, P. Anish, F. Ali, and R. Mohammad. Butterfly transform: An efficient fft based neu- ral architecture design. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
P. Baldi and K. Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1):53-58, 1989.
A. L. Cambridge. The olivetti faces dataset, 1994.
Y. Cheng, F. X. Yu, R. S. Feris. S. Kumar, A. N. Choudhary, and S. Chang. An exploration of deep networks with eirculant projections. In 2015 IEEE International Conference on Computer Vision, 1CCV2015, Santiago, Chile, December 7-13, 2015, pages 2857- 2865. IEEE Computer Society, 2015.
parameter redundancy
K. L. Clarkson and D. P. Woodruff. Numerical linear algebra in the streaming model. In M. Mitzen- macher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 205 214. ACM, 2009.
J. Cooley and J. Tukey. An algorithm for the machine calculation of complex fourier series. Mathe- matics of Computation, 2990-333333,, 1965.
T. Dao, A. Gu, M. Eichhorn, A. Rudra, and C. Ré. Learning fast algorithms for linear transforms using butterfly factorizations. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1517-1527. PMLR, 2019.
T. Dao, N. S. Sohoni, A. Gu, M. Eichhom, A. Blonder, M. Leszezynski, A. Rudra, and C. R. ec. Kaleidoscope: An efficient, learnable representation for all structured linear maps. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
D. Davido, Gabrilovich, and Markovitch. Parameterized generation of labeled datasets for text categorization based on a hierarchical directory. In 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '04, pages 250-257, 2004.
J. Deng, W. Dong, R. Socher, L.-J. Li. K. Li, and L. Fei-Fei. ImageNet: A Lcale-Scale Hierarchical Image Database. In CVPR09, 2009.
10

---

Under review as a conference paper at ICLR 2021
M. Denil, B. Shakibi, L. Dinh, M. Ranzato, and N. de Freitas. Predicting parameters in deep learn- ing. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013., pages 2148-2156 2013.
C. Ding, S. Liao, Y. Wang. Z. Li, N. Liu, Zhuo, C. Wang, X. Qian, Y. Bai, G. Yuan, Ma, Y. Zhang,, J. Tang, Q. Qiu, X. Lin, and B. Yuan. Circnn: accelerating and compressing deep neural networks using block-circulant weight matrices. In Proceedings of the 50th Annual IEEF/ACM International Symposium Microarchitecture, MICRO 2017, pages 395-408. ACM, 2017.
K. He, X. Zhang, Ren, and Sun. Identity mappings in deep residual networks. In Computer Vision ECCV 2016 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV, volume 9908 of Lecture Notes in Computer Science, pages 630-645. Springer, 2016.
J. Hu, L. Shen, S. Albanie, G. Sun, and E. Wu. Squeeze-and-excitation networks. IEEE Trans. Pattern Anal. Mach. Intell., (088))2011-20222 2020.
N. Imamoglu, Y. Oishi, X. Zhang, Y. F. G. Ding, T. Kouyama, and R. Nakamura. Hyperspectral image dataset for benchmarking on salient object detection. In Tenth International Conference on Quality of Multimedia Experience, (QoMEX), pages 1-3, 2018.
Indyk, A. Vakilian, and Y. Yuan. Learning-based low-rank approximations. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buce E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Process- ing Systems 2019, NeurlPS 2019, pages 7400-7410, 2019.
V. Jain, N. Pillai, and A. Smith. Kac meets johnson and lindenstrauss: memory-optimal, fast transform. arXiv, 03 2020.
W. Johnson and J. Lindenstrauss. Extensions of lipschitz maps into hilbert space. Contemporary Mathematics, 26: 26:189 189-8996,, 01 1984. doi: 10. 10.199//oom/002677774000
K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems 29: Anmual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain. pages 586-594, 2016.
Krahmer and R. Ward. New and improved johnson-lindenstraus embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 13:1269-1281, 06 2011. doi: 10. 1137/100810447.
A. Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 2012.
Y. LeCun and C. Cortes. MNIST handwritten digit database, 2010.
N. Lee, T. Ajanthan, and H. S. Torr Snip: single-shot network pruning based on connection sen- sitivity. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net 2019.
Y. Li and H. Yang. Interpolative butterfly factorization. SIAM J. Scientific Computing, 39(2), 2017. 2017.
Y. Li, H. Yang, E. R. Martin, K. L. Ho. and L. Ying. Butterfly factorization. Multiscale Model. Simul,, 13(2):714-732, 2015.
Z. Lu, V. Sindhwani, and T. N. Sainath. Learning compact recurrent neural networks. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016, pages 5964. IEEE, 2016.
M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz. Building large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313-330, 1993. URL https: stttts://werr //www.
aclweb. org/ http///tthoooyy33-/11
E. Michielssen and A. Boag. A multilevel matrix decomposition algorithm for analyzing scattering from large structures. IEEE Transactions on Antennas and Propagation, 1486)11086-1099, 1996.

---

Under review as a conference paper at ICLR 2021
D. C. Mocanu, E. Mocanu, P. Stone, P. H. Nguyen, M. Gibescu, and A. Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Communicationss 9:2383, 2018. doi: 10.1038/s41467
M. Moczulski, M. Denil, J. Appleyard, and N. de Freitas. ACDC: structured efficient linear layer. In Y. Bengio and Y. LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, 2016.
M. O'Neil, F. Woolfe, and V. Rokhlin. An algorithm for the rapid evaluation of special function transforms. Applied and Compulational Harmonic Analysis, 28(2):203 226, 2010.
T. N. Sainath, B. Kingsbury, V. Sindhwani, E. Arisoy, and B. Ramabhadran. Low-rank matrix Factorization for deep neural network training with high-dimensional output targets. In IEEE International Conference Acoustics, Speech and Signal Processing. ICASSP 2013, Vancouver, BC, Canada, May 26-31, 2013, pages 6655-6659. IEEE, 2013.
T. Sarlós. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 143-152. IEEE Computer Society, 2006.
D. S. Seljebotn. WAVEMOTH-FAST SPHERICAL HARMONIC TRANSFORMS BY BUTTER- FLY MATRIX COMPRESSION, The Astrophysical Journal Supplement Series, 199(1):5, 2012.
V. Sindhwani, T. N. Sainath, and S. Kumar. Structured transforms for mootl-ttt deep learning. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neu- ral Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 3088-3096, 2015.
M. Tan and Q. Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6105-6114 14. PMLR, 2019.
A. T. Thomas, A. Gu, T. Dao, A. Rudra, and C. Ré. Learning compressed transforms with low dis- placement rank. In Advances in Neural Information Processing Systems 31; Annual Conference on Neural Information Processing Systems 2018, pages 9066-9078, 2018.
E. F. Tjong Kim Sang and F. De Meulder. Introduction to the CoNLL-2003 shared task: Language- independent named entity recognition. In Proceedings of the Seventh Conference on Natural Lan- guage Learning at HI.T-NACII. 2003, pages 142-147, 2003. /tIlhttss::/ www. www..ac. acc web.
org/anthologg oogy/oyyy////oooooo W03-0411
S. Verdenius. M. Stol, and P. Forré. Pruning via iterative ranking of sensitivity statistics. CoRR, abs/2006.00886, 2020.
C. Wang, G. Zhang, and R. B. Grosse. Picking winning tickets before training by preserving gradient flow. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Z. Yang, M. Moczulski, M. Denil, N. de Freitas, A. J. Smola, L. Song, and Z. Wang. Deep fried convnets. In 2015 IEEE International Conference on Computer Vision ICCV 2015, pages 1476- 1483. IEEE Computer Society, 2015.
J. Ye, L. Wang, G. Li, D. Chen, S. Zhe, X. Chu, and Z. Xu. Learning compact recurrent neural networks with block-term tensor decomposition. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018 pages 9378-9387. IEEE Computer Society, 2018.
12

---

Under review as a conference paper at ICLR 2021
A BUTTERFLY DIAGRAM FROM SECTION 1
Figure referred to the introduction is given here.
10.1
30.0
131
13.0
Figure 6: A 16 x 16 butterfly network represented 4-layered graph on the left, and product of sparse matrices on the right. The white entries are the non-zero entries of the matrices.
B PROOF PROPOSITION
The proof of the proposition will use the following well known fact (Lemma B. below) about FJLT (more generally, JL) distributions (see Ailon and Chazelle (2009;; Ailon and Liberty (200); Krahmer and Ward (211h).
Lemma B.1. Let x E R be a unit vector, and let J E Rx be a matrix drawn from an FJLT distribution. Then for all e < with probability at least - -
||x J"| S
(2)
By Lemma B.1 we have that with probability at least 1 c -2(()116")
|x Ju J1x|| I <||x|| =c
(3)
Henceforth, we condition on the event |x - 17 J/x norm ||]]| of W:
S El [|x|| Therefore, by the definition spectral
|Wx W J J1x|1 < <IIWII Now apply Lemma B. again on the vector W Jix and transformation J2 to get that with proba- bility at least 1 ((kad)
(4)
15 JW S [f -
(5)
Henceforth, we condition on the event W[ JIx JJ J2W J Jıx| s J[ To bound the last right hand side, we use the triangle inequality together with 4
[ || <||WI| S []] + t).
(6)
Combining 5 and gives:
[[W JIx JS J2W Jf JIx|| < + +).
13

---

Under review as a conference paper at ICLR 2021
Finally,
J = J[ -1) + [WJ -xx)ll
S <|[W][[11 + = 3
+ W|
(8)
where the first inequality is from the triangle inequality together with and (7). and the second inequality is from the bound on The proposition is obtained by adjusting the constants hiding inside the ?() notation in the exponent in the proposition statement.
C PROOF OF THEOREM
We first note that our result continues to hold even if B in the theorem replaced by any structured matrix. For example the result continues to hold if B is an E x n matrix with one non-zero entry per column, as the case with a random sparse sketching matrix Clarkson and Woodruff (2009). We also compare our result with that Baldi and Hornik (1899; ; Kawaguchi (2016).
Comparison with Baldi and Hornik (1989) and Kawaguchi (2016): The critical points of the encoder-decoder network are analyzed in Baldi and Hornik (1989). Suppose the eigenvalues of Ymu > and k S m S. n. Then they show that corresponding to critical point there is I S [mn] such that the loss at this critical point is equal to tr(YY")
Y (XX")" XXY are 71 >
Eier %. and the critical point is a local/global minima if and only if / = [k:]. Kawaguchi (2016)
later generalized this to prove that local minima is global minima for an arbitrary number of
hidden layers in a linear neural network if m < n. Note that since & < n and m S n in Theorem |
replacing X by BX in Baldi and Hornik 1989) or Kawaguchi 2016) does not imply Theorem | as it is.
Next, we introduce a few notation before delving into the proof. Let (Y -YYY and vee(r) e IRndd is the entries of arranged vector in column-first ordering, (V (Vve(Dz)((()) E Bmn and (V (())) E A denote the partial derivative of L(Y) with respect to the parameters in vec( (ee) and vec vec(E"") respectively. Notice that V Ver C(Y) and Vvl(ET))((() are row vectors of size mk and &e respectively. Also, let Pn denote the projection matrix of D, and hence if D is matrix with full column-rant then PD D(D" D)-1 " The x identity matrix is denoted as In. and for convenience of notation let X B X. First we prove the following lemma which gives an expression for D and E if D ((Y) and V are zero
Lemma C.1 (Derivatives with respect to D and E).
1. V Vox(Dr) vec(r) @ (E 8) and
2. V V ((X) vec(r) (D X)T
Proof.
1. Since ((Y) = = vec(r),
V VVo(DD))(()) vec(r) V vec(r) =
ETT, -DT)) vec(r) @ (E- X)J) VieeDDr) vec(r) (Im 3 (E-
2. Similarly,
V (ee(ET)<(]) = veo(r)" V vec())))e(() = (VeC)EE) (8² S". -E"DD") vec(r) X-) V Vroe(E))ec(EE") vec(r)) (D (D&X')
Assume the rank of D is equal to p. Hence there is an invertible matrix C E Rexk such that D D. C is such that the last k p columns of D are zero and the first p columns of D are linearly independent (via Gauss elimination). Let E C-1, E. Without loss of generality it can be assumed D dRd and e. RRxd by restricting restricting D to its first p columns (as the remaining
14

---

Under review as a conference paper at ICLR 2021
zero) and E to its first Claims C.I and C.2 aid us the completing the proof of the theorem. First the proof of theorem is completed using these claims, and the end the two claims are proved. Claim C.1 (Representation at the critical point).
Hence, D is full column-rank matrix of rank p, and DE DE.
1. E - X7)-
2. DÉ PDYX* X
Claim C.2.
2. PDΣ= EPD P
We denote E(B) E for convenience. Since Σ is a real symmetric matrix, there an orthogonal matrix U consisting of the eigenvectors of Σ, such that Σ U A U², where A is a m x m diagonal matrix whose first é diagonal entries are ...... Xς and the remaining entries are zero. Let ui....,, Um be the columns of U. Then for E [d]. u, is the eigenvector of Σ corresponding to the eigenvalue X, and {ue+l,...: udd) are the eigenvectors of Σ corresponding to the eigenvalue 0.
Note that PUTD of CーDØDOTDNNンン = UTP and from part two of Claim C.2 have
=EP E S(UPUTBUT) U. -UPPEAU"=UUPPEE"" PU
(9)
=UA
(10)
POTDA= -PUTD
(11)
Since PUrD commutes with A, P Por B is block-diagonal matrix comprising of two blocks P1 and
P2: the first block Pi an x l diagonal block, and P2 a (m E) x (m - E) matrix. Since
PUT is orthogonal projection matrix of rank its eigenvalues are with multiplicity p and 0 with multiplicity m p. Hence most diagonal entries of P1 are and the remaining are Finally observe that
((Y) = =t((( - Y) - -)))
= -2r(Y)²) + (r((Y"))
=tr(YY")) = ( ET
+
The second line in the above equation follows using the fact that tr(YY = " the third line in the above equation follows by substituting Y = PpY X (X (X-X)-11
x")-1.X x. (from part two
of Claim C.I and the last line follows from part two of Claim C.2 Substituting Σ = U A AUT and Pp = UP UP UT the above equation we have,
L(Y) ir(rY))) tuUU AUT)
-r((Y"))- u
The last line the above equation follows from the fact that tr(UP D AUT) = tr(PUTD AUTU) tr( tr(Per (frrp/A)))) RA). From the structure of Por 5 and A it follows that there is subset [6] /4| S p such that tr(Pur (PTTDA) Eier 74. Hence, L(Y) tr(YYT) - Eier d
Since P3 UPP UUTTUU UT, there is a x p invertible matrix M such that
D = (U V)r M and E = (
where V is block-diagonal matrix consisting of two blocks V1 and V2: Vi is equal to Le, and V/ is an (m 6) (m f) orthogonal matrix, and l' is such that / C I' and [/'| The relation for É in the above equation follows from part one of Claim C.1 Note that C [E]. then / = I', that is I consists of indices corresponding to eigenvectors of non-zero eigenvalues.
Recall that ò was obtained by truncating the last p zero of DC, where C was
15

---

Under review as a conference paper at ICLR 2021
k x k invertible matrix simulating the Gaussian elimination. Let [M] (x- denoted the p matrix obtained by augmenting the columns of M with (k 1--p p) zero columns. Then
D (Mxx)
Similarly, there is a x (k- p) matrix N such that
E (I
where M- denotes the k x p matrix obtained by augmenting the rows of M-1 with the rows of N. Now suppose 1 * [k]. and hence 1' * [k]. Then will show that there matrices D' and E' arbitrarily close to D and E respectively such that if Y D'E'X X then L(Y") L(Y). There an E [k] \. I', and E I' such that Àa > As (As could also be zero). Denote the columns of the matrix UV as {u1:---
U. and observe that v2 uy for i [4] (from the structure of V). For <> let uny = (1 + 2 - (uy + cua). Define U as the matrix which is equal to UV except that the column vector Us in UV is replaced by ug in U². Since E [k] S [4] and & I', Va Uaa and UU, = Ip. Define
= --U,,MMO (C= and E' CI (XX))
and let Y D'E'X. Now observe that, D'E' UXX and that
- ~ 1 1 An) = C(Y)
(2
(Au - Xa)
SEI
Since e can be set arbitrarily close to zero, it can be concluded that there are points in the neigh- bourhood of Y such that the loss these points less than L(Y). Further, since L is convex with respect to the parameters D (respectively E), when the matrix is fixed (respectively D is fixed) Y is not local maximum. Hence, if I * [k] then Y represents saddle point, and in particular Y is local/global minima if and only if = [k].
Proof of Claim C.7 Since V Voo(EET) ((X) is equal to zero, from the second part of Lemma C.I the
following holds,
- - D=0 D
XX EJ D=
Taking transpose on both sides
D'DEXXT DT
(12)
Substituting DE as DE in Equation
12 and multiplying Equation 12 by CT on both the sides from
the left, Equation 13 follows.
D'DEXXT== =D"X""
(13)
Since D is full-rank, we have
x= (Drブ) -DTX"
(14)
and,
DE = PXXX
(15)
Proof of Claim C.2 Since V Vvec( Dz ( ((Y) is zero, from the first part of Lemma C.I the following holds.
EX(Y Y)T -Y- + D E
EXYT EX Y =0
(16)
Substituting ET. DT ÉT, DT in Equation 12 and multiplying Equation 16 by C-1 on both the sides from the left Equation I follows.
-
(17)
16

---

Under review as a conference paper at ICLR 2021
Taking transpose of the above equation have,
=
(18)
From part 1 of Claim C.1
follows that É has full row-rank, and hence EXXT ET invertible.
Multiplying the inverse of EXXTE ET from the right on both sides and multiplying EB from the left on both sides of the above equation have,
ËBδ
(19)
This proves part one of the claim. Moreover, multiplying Equation 18by Dr from the right on both sides
D"
=
Pb)
-XXT PD
The second line the above equation follows by substituting = PxXx""XXXXX" (from part
of Claim C.1 Substituting = Y (XX7) - in the above equation we have
PDEPD E PD
Since P = Pn. and ΣT E, also have ΣP, E.
D ADDITIONAL TABLES AND PLOTS FROM SECTION 6
D.1 PLOTS FROM SECTION 6.
Figure displays the number of parameters in the dense linear layer of the original model and in the replaced butterfly based network. Figure(Jreportt the results for the NLP tasks done part of experiment in Section 6. Figure [ displays the number of parameter in the original model and the butterfly model. Figures 10 and H reports the training and inference times required for the original model and the butterfly model in each of the experiments. The training and and inference times in Figures 10 and 11 are averaged over 100 runs. is the same as the right part of Figure but here we compare the test accuracy of the original and butterfly model for the the first 20 epochs.
0106 aet DINI Noniibeleett CIAA Mnni
CARLL 2010
CALL
Pee Todkue Fruits
mode
Homol inodel
Figure 7: Number of parameters the dense linear layer of the original model and the replaced butterfly based architecture; Left: Vision data, Right: NLP
D.2 PLOTS FROM SECTION 6.2
Gaussian and Gaussian are Gaussian matrices with rank 32 and 64 respectively. Rank Gaussian matrices are constructed as follows: orthonormal vectors of size 1024 are sampled at random and the columns the matrix are random linear combinations of these vectors determined by choosing the coefficients independently and uniformly at random from the Gaussian distribution with mean and variance 0.01. The data matrix for MNIST is constructed follows: each row corresponds
Data Matrices:
The data matrices are as Table 2
image represented 28 x
17

---

Under review as a conference paper at ICLR 2021
PM0
VERIMOO
400.00
00000
DENSENT
300.000
3020000
1000MM
10/400
Figure 8: Total number of parameters in the original model and the butterfly model; Left: Vision data, Right: NLP
Normel
0.0
Srow
0.0
0
100
200
400
500
# ggaatannt slap
Figure 9: Right: Final F1 Score for different NLP models and data sets. Left: comparison in the first few epochs with different models on CoNLL-003 Named Entity Recognition (English) with the flair's Sequence Tagger
6:2
0.831
Figure 10: Training/Inference times for Vision Data; Left: Training time, Right: Inference time
28 matrix (pixels) sampled uniformly at random from the MNIST database of handwritten digits (LeCun and Cortes 2010) which is extended to a 32 x 32 matrix by padding numbers close to zero and then represented as vector of size 1024 in column-fine ordering Similar to the MNIST every row of the data matrix for Olivetti corresponds to an image represented as a 64 x 64 matrix sampled uniformly random from the Olivetti faces data set (Cambridge 1994), which represented as a vector of size 4096 in column-fiin first ordering. Finally, for HS-SOD the data matrix is 1024 x 768 matrix sampled uniformly at random from HS-SOD dataset for hyperspectral images from natural scenes (Imamoglu et al. 2018).
Figure reports the losses for the Gaussian Olivetti, and Hyper data matrices.
CClose to zero entries sampled uniformly random according to Gaussian distribution with mean zero and variance 0.01.
18

---

Under review as a conference paper at ICLR 2021
C30
1:1
RAVA
Figure 11: Training/Inference times for NLP; Left: Training time, Right: Inference time
80
60
Test accuracy
40
20
Normal (SGD)
BF (SGD)
Normal (Adam)
BF (Adam)
0
0
10
15
20
Epoch
Figure 12: Comparison of test accuracy in the first epochs with different models and optimizers on CIFAR-10 10 with PreActResNet18
210
300
100
Turcate
Saaoere buttrrfy autorookee
600
Figure 13: Approximation error on data matrix with various methods for various values of k. From
left to right: Gaussian 2, Olivetti, Hyper
MISSING PLOTS FROM SECTION
In this section we state a few additional cases that were done as part of the experiment Section 7
Figure 14] compares the test errors of the different methods in the extreme case when l 1. Figure 15 compares the test errors the different methods for various values f. Figure [6 shows the test error for 20 and 10 during the training phase HS-SOD. Observe that the butterfly
19

---

Under review as a conference paper at ICLR 2021
learned is able to surpass sparse learned after merely few iterations. Finally Table 4 compares the test error for different values and k.
Figure 14: Test errors on HS-SOD for f 20 and l = 1, zoomed on butterfly and sparse learned in the right
Figure 15: Test error when = 10, & = [10, 20, 20,40, 60, 80] on HS-SOD, zoomed on butterfly and sparse learned in the right
2.0
Butterfly Learned
1.
Sparse Learned
Test
Sparse Random
Dense Random
10
0.5
0.0
500
1000
1500
2000
2500
#Step
Figure 16: Test error when k = 10, f = 20 during the training phase on HS-SOD
F BOUND ON NUMBER OF EFFECTIVE WEIGHTS IN TRUNCATED BUTTERFLY NETWORK
butterfly network for dimension n, which we assume for simplicity to an integral power of 2, is log n layers deep. Let p denote the integer log The set of nodes in the first (input) layer will be denoted here by (0) They are connected to the set of n nodes (L) from the next layer, and so on until the nodes (r) the output layer. Between two consecutive layers Vii and v(++), there are 2n weights, and each node in (+) adjacent to exactly two nodes from (i+1))
When truncating the network, we discard all but some set S(r) C V(r) of most nodes in the last layer. These nodes connected to subset S(p-1) v(p-1) of most 26 nodes from the
20

---

Under review as a conference paper at ICLR 2021
k, E, Sketch
Hyper
Cifar-10
Tech
1, 5, Butterfly
0.0008
0.173
0.188
1, 5, Sparse
0.003
1.121
1.75
1, Random
0.661
4.870
3.127
I, I0, Butterfly
0.0002
0.072
0.051
1, 10, Sparse
0.002
0.671
0.455
1, 10, Random
0.131
1.82
1.44
10, 10, Butterfly
0.031
0.751
0.619
10, 10, Sparse
0.489
6.989
7.154
10, 10, Random
5.712
26.133
18,805
10, 20, Butterfly
0.012
0,470
0.568
10, 20, Sparse
0.139
3.122
3.134
10, 20, Random
2.097
9.216
8.22
10, 40, Butterfly
0.006
0.111
10, 40, Sparse
0.081
0.991
10, 40, Random
0.544
3.304
20, 20, Butterfly
0.058
1.38
20, 20, Sparse
0.229
8.14
20, 20, Random
4.173
15.268
20, 40, Butterfly
0.024
0.703
20, 40, Sparse
0.247
3,441
20, 40, Random
1.334
6,848
30, 30, Butterfly
0.027
1.25
30, 30, Sparse
0.749
7.519
30, 30, Random
3.486
13.168
30, 60, Butterfly
0.014
0.409
30, 60, Sparse
0.331
2.993
30, 60, Random
2.105
5.124
Table 4: Test error for different & and k:
preceding layer using at most 2 weights. By induction, for all i 2 O, the set of nodes S(p-i) C ((--1) is of size at most 2 l, and is connected to the set S(p-i-1) C (p-ii-1 using at most 2 . weights.
Now take [log (n/ By the above, the total number of weights that can participate a path connecting some node in 5(P) with some node in ((--k) is at most
26 + 2 S 4n.
From the other direction, the total number of weights that can participate in path connecting any node from (()) with any node from (p=-k) is 2n times the number of layers between, or more precisely:
2n(p - k)) = 2n(gog n [log(nn()] s 2n(log2 n logz + = 2n + 1).
The total is 2n log + 6n, as required.
21


Reviews:
[{"review_id": "u3JSxT0Oq8R", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies “butterfly networks”, where, a logarithmic number of linear layers with sparse connections resembling the butterfly structure of the FFT algorithm, along with linear layers in smaller dimensions are used to approximate linear layers in larger dimensions. In general, the paper follows the idea of sketching to design new architectures that can reduce the number of trainable parameters.  In that regard, the paper is very appealing, as it shows that replacing linear layers with the butterfly networks does not result in any loss in performance. \n\nThe paper’s aim is to establish that linear layers can be replaced by butterfly networks and uses three different experiments to show this. The experiments do lend evidence to the claim that butterfly networks do not lead to a loss in performance. \n\nThe paper also present some theoretical results to show that the using butterfly networks sampled from the FJLT family preserves certain metric. However, my opinion is that Theorems 1 and 2 are mostly direct consequences of existing theorems in the sketching literature.\n\nFinally, although I appreciate the experiments in the paper, I feel strongly that the paper lacks motivation. The idea of sketching and using FJLT transforms have had a great impact on numerical linear algebra and generally in reducing computational complexity of algorithms. However, it is unclear from this paper what the expected impact is. Probably the authors could focus more on this. Possible directions are to show improved training times, or maybe even showing that such networks are more resilient towards overfitting. \n\nAs interesting as the experiments are, the paper needs a better motivation and further exploration of the utility of the ideas presented. For example, can using butterfly networks improve theory or practice of deep learning/machine learning? I do like the paper, but the paper can be much stronger and much more appealing if the motivation is better justified. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BQRr-tMzMQl", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I list the strong and weak points in the following:\n\n### Strong points\n\n- It is a novel idea (only to my knowledge) to combine the butterfly network and FJLT to optimize the neural network architectures. Specifically, the proposed method replaces a dense linear layer by a composition of three layers, which are smaller and can be computed faster by FJLT. \n\n\n### Weak points\n\n- The paper says that the proposed method would speed up the training. But there is no quantitative argument. Also the paper does not report the computing time or memory used in all the experiments.\n\n- In Definition 4.1, $n$ is required to be a power of 2. And in the experiments, it seems that all the $n$ are powers of 2 (except Tech). What do one do if $n$ is not a power of 2? \n\n- In all the experiments, the final hidden layer is replaced by the proposed architecture. Is there any reason for doing this? How should one choose which layer(s) to be replaced?\n\n- It is argued that by replacing a dense layer with a truncated butterfly network and a dense layer, the number of parameters is reduced from $kn$ to $k\\ell+O(n\\log\\ell)$. But since the Big O can hide potentially large constants, I wonder how many parameters are used exactly. I expect the paper would report the parameter numbers in the experiments. \n\n- Theorem 1 shows that replacing a dense layer by two truncated butterfly networks and a dense layer will not be too different from the original network. But this holds only when $J_1$ and $J_2$ are sampled from the FJLT distribution. Since the weights $J_1$ and $J_2$ are updated through the training process, the theorem will only hold at initialization. Then what is the point of Theorem 1?", "extra_scores": {}, "extra_text": {}}, {"review_id": "2pXWN0DtXj", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to impose a particular sparsity structure (butterfly network) to replace dense connected layers in deep neural networks. It is motivated by the theoretical results involving the Fast Johnson Lindenstrauss Transform (FJLT). The work is well motivated and experimental results validate the theoretical findings. However, it is not clear the advantage for the case of image datasets as CIFAR10 and CIFAR100. I have the following comments and questions that should be clarified to evaluate the relevance of the results:\n-\tWhen comparing with other architectures on image classification tasks (CIFAR10 and CIFAR 100), what is the dense layer that is replaced by the butterfly structure? Most very well-known architectures are based on large concatenation of convolutional layers with a dense layer at the end. Is this last layer the one that is replaced? What is the compression attained by this replacement? \n-\tIn this architecture, the sparsity pattern is fixed, and it seems to work very well for the dataset used in the paper. It would be interesting to provide some insights on why this particularly structure works well on natural data. Is there any property on datasets that makes butterfly pattern optimal?\n-\tFor natural images, it is well known that sparsity structure imposed by convolutional layers is optimal because of local structure of natural images. I think a comparison replacing a convolutional layer by a butterfly layer could bring some useful insights.\n-\tTheorem 1: What is Omega in the exponent? I couldn’t find its definition.\n-\tFigure 1(a): The small difference between normal and BF models seems not to be statistically significant. It would be good to show some variability of results (error bars).\n-\t For the results of Figure 1(b), it would be also useful to report the training time reduction and model compression attained by the normal and BF models.\n-\tFigure 1(b): The starting point for the four methods should be the same. Please include in the plot the Test Accuracy at the beginning (epoch 0).\n-\tFigure 1(b): Please extend the plots beyond epoch 20 to see how the values are stabilized for the four methods.\n-\tQuality of Figures, for example Fig 3, must be improved (too small fonts, blurred, etc.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "2MXhCez_-Sb", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper provides an interesting and novel use of butterfly factoziations in encoder-decoder networks. Specifically, the paper proposes replacing the \nencoder with a truncated butterfly network followed by a dense linear layer. The parameters are chosen so as to keep the number of weights in the (replaced) encoder near linear in the input dimension. The authors provide a theoretical result related to auto-encoder optimization.\n\n######\n\nI vote for accepting the paper. The main reason is for my vote is that the main idea introduced is novel and the algorithmic contribution is substantial. \n\n######\n\npros \n+ The proposed truncated butterfly network is novel. Aside from the algorithmic contribution, the theorem in the paper raise important questions about\nthe optimization landscape of butterfly networks. \n+ The paper is clearly written and well justified \n+ Exhaustive literature survey and background on relevant work in both the matrix factorization and neural networks front\n\n######\n\ncons \n- The beginning of section 7 needs to be expanded with more details on the original Indyk et al 2019 paper -- the authors mention that they use the same setting as \nthe 2019 paper but the details on how Indyk et al train their network are lacking without looking up the original paper. \n\n- I think that low matrix approximation experimentation (Sec 7) can be more thorough. Why are only three datasets (in Table 3) used? Additionally and more importantly, Table 4 shows the approximation results for low values of k (max of 30) -- what happens when k=(min(n,d))? Also, the error is measured with respect to the best rank k approximation of X (the eq. following eq. 20) While this way of measuring the error is often used in the low rank matrix approximation literature it is not very informative of the actual approximation quality of \\tilde X. It could well be the case that \\tilde X = X_k but the error ||X-\\tilde X||_F/||X||_F might  be poor hence this way of measuring the approximation performance is a better indicator of how well X is actually approximated in practice.   \n\n######\n\nquestions: see the above section ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows that linear layers can be replaced by butterfly networks. Put simple, the paper follows the idea of sketching to design new architectures that can reduce the number of trainable parameters and also gives the theoretical and empirical analysis to validate this claim. In this regard, the paper would be  appealing.  But the theoretical results given in this paper are incremental.
Decision: Reject