Title: THE EXPRESSIVE POWER OF DEEP NEURAL NETWORKS WITH CIRCULANT MATRICES

Abstract: Recent results from linear algebra stating that any matrix can be decomposed into products of diagonal and circulant matrices has lead to the design of compact deep neural network architectures that perform well in practice. In this paper, we bridge the gap between these good empirical results and the theoretical approximation capabilities of Deep diagonalcirculant ReLU networks. More precisely, we first demonstrate that a Deep diagonalcirculant ReLU networks of bounded width and small depth can approximate a deep ReLU network in which the dense matrices are of low rank. Based on this result, we provide new bounds on the expressive power and universal approximativeness of this type of networks. We support our experimental results with thorough experiments on a large, real world video classification problem.

1. INTRODUCTION:

Recent progress in deep neural networks came at the cost of an important increase of model sizes. Nowadays, state-of-the-art architectures for common tasks such as object recognition typically have tens of millions of parameters (He et al., 2016) and up to a billion parameters in some cases (Dean et al., 2012) . Best performing (ensemble) models typically combine dozens of such models, and their size can quickly add up to ten or twenty gigabytes. Large models are often more accurate, but training them requires time and large amounts of computational resources. Even when they are trained, they remain difficult to deploy, especially on mobile devices where memory or computational power is limited.

In linear algebra, it is common to exploit structural properties of matrices to speedup computations, or reduce memory usage. Cheng et al. (2015) have applied this principle in the context of deep neural networks, and proposed a network architecture in which large unstructured weight matrices have been replaced with more compact matrices with a circulant structure. Since any n-by-n circulant matrix can be represented in memory using only a vector of dimension n, the change resulted in a drastic reduction of the model size (from 230MB to 21MB). Furthermore, Cheng et al. have shown empirically that their network architecture can be almost as accurate as the original network. Moczulski et al. (2015) have proposed a more principled approach leveraging a result by Huhtanen & Perämäki (2015) stating that any matrix A ∈ C n×n can be decomposed into 2n -1 diagonal and circulant matrices. They use this result to design Deep diagonal-circulant ReLU networks. However their experiments show good results even with a small number of factors (down to 2 factors), suggesting that Deep diagonal-circulant ReLU networks can achieve good approximation error, even with few factors.

In this paper, we bridge the gap between the good empirical results observed by Moczulski et al. (2015) , and the theoretical approximation capabilities of Deep diagonal-circulant ReLU networks. We prove that Deep diagonal-circulant ReLU networks with bounded width and small depth can approximate any dense neural network. We obtain this result by showing that any matrix A can be decomposed into 4k + 1 diagonal and circulant matrices where k is the rank of the matrix A. In practice, this result is more useful than the one by Huhtanen & Perämäki since one can rely on a low rank SVD decomposition of A while controlling the approximation error.

In addition to this theoretical contribution, we also conduct thorough experiments on synthetic and real datasets. In accordance with the theory, our experiments demonstrate that we can easily tradeoff accuracy for model size by adjusting the number of factors in the matrix decomposition. Finally we evaluate the applicability of this approach on state-of-the-art neural network architectures trained for video classification on the Youtube-8m Video dataset (over 1TB of training data) . This experiment demonstrates that Deep diagonal-circulant ReLU networks can be used to train more compact neural networks on large scale, real world scenarios.

2. RELATED WORK:

A variety of techniques have been proposed to build more compact deep learning models. A first category of techniques aims at compressing a trained network into a smaller model, without compromising the accuracy. For example model distillation (Hinton et al., 2015) is two step training procedure: first a large model is trained to be as accurate as possible, second a more compact model is trained to approximate the first one. Other approaches have focused on compressing the network by reducing the memory, at the level of individual weights, (for example, using weight quantization (Han et al., 2016) or parameter pruning) or at the level of weight matrices, using low rank decomposition of the original weight matrix (Sainath et al., 2013) or using sparse representations (Collins & Kohli, 2014; Dai et al., 2018; Liu et al., 2015) .

Instead of compressing the network a posteriori, several researchers have focused on designing models that are compact by design. This approach has several benefits, but most importantly, it reduces memory footprint, both required during training and inference. Chen et al. (2015) have proposed to compress weight matrices by using hashing functions to map several matrix coefficients into the same memory cell. The techniques works well in theory, but suffers from poor performance on modern GPU devices due to irregular access patterns.

In their paper, Cheng et al. (2015) observed that fully connected layers (which typically occupy 90%1 . of the total number of weights) are often used to perform simple dimensionality reduction operation between layers of different dimension. The idea of replacing large weight matrices from fully connected layers with more compact circulant layers comes from a result by Hinrichs & Vybíral (2011) that have demonstrated that circulant matrices can be use to approximate the Johson-Lindenstrauss transform, often used to perform dimensionality reduction. Building on this result Cheng et al. proposed to replace the weight matrix of a fully connected layer by a circulant matrix initialized with random weights. The resulting models achieve good accuracy, with the random circulant matrix, but even better when the weights of the circulant matrix are trained with the rest of the network using a gradient based optimization algorithm. This suggests that such layers, often perform more than simple random projections, and that more expressive fully connected layers are beneficial to the overall accuracy of the model.

Fortunately, more general linear transforms can also be described using circulant matrices or other structured matrices, at the cost of using more of them. Müller-Quade et al. (1998) and Schmid et al. (2000) have demonstrated this formally by showing that any matrix can be decomposed into the product of diagonal and circulant matrices, and Moczulski et al. (2015) have proposed a compact neural network architecture based on this decomposition that exhibit good accuracy in practice. Other researchers have investigated using alternative structures such as Toeplitz (Sindhwani et al., 2015) , Vandermonde (Sindhwani et al., 2015) or Fastfood transforms (Yang et al., 2015) . Despite demonstrating good empirical results, there have been little theoretical insight to explain the good approximation capabilities of deep neural networks based on structured matrices. Barron (1993) presented the universal approximation theorem which states that any neural network with at least 1 hidden layer and sigmoid non linearity can approximate any function. However, the theorem by Barron (1993) does not bound the width of the neural network and does not consider the training procedure. Since then, substantial theoretical work has been done to evaluate the expressiveness of a neural network as a function of the width (i.e. the number of neurons) and the depth of the network Arora et al. (2018) ; Mhaskar et al. (2017) ; Lin et al. (2017) ; Poole et al. (2016) ; Raghu et al. (2016) ; Telgarsky (2016) ; Mhaskar & Poggio (2016) . In 2000, Hanin (2017) have investigated the approximation capabilities of neural networks with ReLU activations and demonstrated that such networks can approximate any function.

More recently, Zhao et al. (2017) have provided a theoretical study of Deep diagonal-circulant ReLU networks and demonstrated that 2-layers networks of unbounded width are universal approximators. However, these results are of limited interest because the networks used in practice are of bounded width. Unfortunately, nothing is known about the theoretical properties of Deep diagonal-circulant ReLU networks in this case.

3. BUILDING COMPACT DEEP NEURAL NETWORKS USING CIRCULANT MATRICES:



3.1. PRELIMINARIES ON CIRCULANT MATRICES:

A n-by-n circulant matrix C is a special kind of Toeplitz matrix where each row is a cyclic right shift of the previous one as illustrated below.

C = circ(c) =       c 0 c n-1 c n-2 . . . c 1 c 1 c 0 c n-1 c 2 c 2 c 1 c 0 c 3 . . . . . . . . . c n-1 c n-2 c n-3 c 0      

Despite their rigorous structure, circulant matrices are expressive enough to model a variety of linear transforms such as random projections (Hinrichs & Vybíral, 2011) and when they are combined together with diagonal matrices, they can be used to represent an arbitrary transform (Schmid et al., 2000) .

Circulant matrices also exhibit several properties that are interesting from a computational perspective. First, a circulant n-by-n matrix C can be represented using only n coefficients. Thus, it is far more compact that a full matrix that requires n 2 coefficient. Second, the product between a circulant matrix C and a vector x can be simplified to a simple element-wise product between the vector c and x in the Fourier domain (which is generally performed efficiently on GPU devices). This results in a complexity reduced from O(n 2 ) to O(nlog(n)).

In their paper, Huhtanen & Perämäki (2015) have demonstrated that any matrix A ∈ C n×n can be approximated with an arbitrary precision by a product of circulant and diagonal matrices: Theorem 1. (Huhtanen & Perämäki, 2015) For any given matrix A ∈ C n×n , let p be the smallest integer such that A = p i=1 D i S i-1 where D 1 . . . D p are diagonal matrices. Then for any > 0, for any matrix norm • , there exists a sequence of matrices B 1 . . . B 2n-1 where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise, such that B 1 B 2 . . . B 2n-1 -A < , and where S = circ(0, 1, 0, . . . , 0)

Because of their interesting properties, several researchers have considered circulant matrices as a replacement from full weight matrices inside neural networks.

3.2. THEORETICAL PROPERTIES OF DEEP DIAGONAL-CIRCULANT RELU NETWORKS:

There has already been some recent theoretical work on Deep diagonal-circulant ReLU networks, in which 2-layer networks of unbounded width where shown to be universal approximators. These results are of limited interest, because the networks used in practice are of bounded width. Unfortunately, nothing is known about the theoretical properties of Deep diagonal-circulant ReLU networks in this case. In particular, the following questions remained unanswered up to now: Are Deep diagonal-circulant ReLU networks with bounded width universal approximators? What kind of functions can Deep diagonal-circulant ReLU networks with bounded-width and small depth approximate?

In this section, we first define formally diagonal-circulant ReLU networks, and then provide a theoretical analysis of their approximation capabilities.

Definition 1 (Deep ReLU networks). With ReLU (x) = max(0, x), let f A,b (x) = ReLU (Ax + b) for any matrices A ∈ C n×n , and any b ∈ R n . A Deep ReLU network is a function f A l ,b l • . . . • f A1,b1

, where A 1 . . . A l are arbitrary n × n matrices and b 1 . . . b l ∈ C n and where l and n are the depth and the width of the network respectively.

As in Moczulski et al. (2015) , Deep diagonal-circulant ReLU networks can be defined as follows:

Definition 2 (Deep diagonal-circulant ReLU networks). A Deep diagonal-circulant ReLU network is a function f D l C l ,b l • . . . • f D1C1,b1 where D 1 . . . D l ∈ C n×n are diagonal matrices, C 1 . . . C l ∈ C n×n

are circulant matrices, and where l and n are the depth and the width of the network respectively.

To show that bounded-width Deep diagonal-circulant ReLU networks are universal approximators, we first need a proposition relating standard deep neural networks to Deep diagonal-circulant ReLU networks.

Proposition 2. Let N : R n → R n be a deep ReLU networks of width n and depth l, and let X ⊂ R n be a compact set. For any > 0, there exists a deep diagonal-circulant ReLU network N of width n and of depth (2n -1)l such that N (x) -N (x) 2 < for all x ∈ X .

We can now state the universal approximation corrolary: 2015)). The following theorem studies the approximation properties of these small depth networks.

Proposition 3. Let N : f A l ,b l • . . . • f A1,

b1 be a deep ReLU network of width n and depth l, such that each matrix A i is of rank k i , where k i divides n. Let X ⊂ R n be a compact set. For any > 0, there exists a deep diagonal-circulant ReLU network N of width n and of depth (

n i=1 (4k i + 1)) l such that N (x) -N (x) 2 < for all x ∈ X .

This result generalizes Proposition 2, showing that a Deep diagonal-circulant ReLU networks of bounded width and small depth can approximate a deep ReLU network in which the dense matrices are of low rank. Note in the proposition, we require that k i divides n. We conjecture that the proposition holds even without this condition, but we were not able to prove it.

Finally, what if we choose to use small depth network to approximate deep ReLU networks where matrices are not of low rank ? To answer this question, we first need to show the negative impact of replacing matrices by their low rank approximators in neural networks:

Proposition 4. Let N = f A l ,b l • . . . • f A1,b1 be a deep ReLU network, where A i ∈ C n×n , b i ∈ C n for all i ∈ [l].

Let Āi be the matrix obtained by a SVD approximation of rank k of matrix A i . Let σ i,j is the j th singular value of

A i . Define N = f Āl ,b l • . . . • f Ā1,b1 . Then, for any x ∈ C n , we have N (x) -N (x) ≤ (σ l max,1 -1)Rσ max,k σmax,1-1

where R is an upper bound on norm of the output of any layer in N , and σ max,j = max i σ i,j .

Basically, this proposition shows that we can approximate matrices in a neural network by low rank matrices, and control the approximation error. In general, the term σ l max,1 could seem large, but in practice, it is likely that most singular values in deep neural network are small in order to avoid divergent behaviors. We can now prove the result on Deep diagonal-circulant ReLU networks:

Corrolary 2. Consider any deep ReLU network N = f A l ,b l • . . . • f A1,b1

of depth l and width n. Let σ max,j = max i σ i,j where σ i,j is the j th singular value of A i . Let X ⊂ R n be a compact set. For any k dividing n, there exists a deep diagonal-circulant ReLU network

N = f DmCm,b l • . . . • f D1C1,b 1 of width n and of depth m = 4(k + 1)n, such that for any x ∈ X , N (x) -N (x) < (σ l max,1 -1)Rσ max,k σmax,1-1

, where R is an upper bound on the norm of the outputs of each layer in N .

Proof. Let N = f Āl ,b l • . . . • f Ā1,b1

, where each Āi is the matrix obtained by a SVD approximation of rank k of matrix A i .

With proposition 4, we have an error bound on N (x) -N (x) . Now each matrix Āi can be replaced by a product of k diagonal-circulant matrices. By lemma 1, this product yields a Deep diagonal-circulant ReLU networks of depth m = 4(k + 1)n, strictly equivalent to N on X . The result follows.

4. EMPIRICAL EVALUATION:

The experiments that we present in this section aim at answering the following questions. First question: what is the impact of increasing the number of diagonal-circulant factors on the accuracy of the network? To answer this question, we conduct a series of experiments on a synthetic classification dataset with an increasing number of factors. As we will show, the results match our theoretical analysis from Section 3. Second question: can this approach be useful to build more compact models in the context of large scale realworld machine learning applications. To answer this second question, we build a deep diagonal-circulant neural network architecture for video classification. The architecture is based on state-of-the-art architecture initially proposed by Abu-El-Haija et al. (2016b) and later improved by Miech et al. (2017) in involve several large layers that can be made more compact using circulant matrices as done in Araujo et al. (2018) . As we will show, the approach demonstrate good accuracy and can be used to build a more compact network than the original one.

4.1. IMPACT OF THE NUMBER OF DIAGONAL-CIRCULANT FACTORS ON ACCURACY:

Experimental setup The dataset is generated using the make classification2 function from Scikit-Learn (Pedregosa et al., 2011) . It is made of 10000 examples, 5 variables, 2 classes and 2 clusters for each class. We train a neural network with 3 hidden layers of 1024 neurons each. We used a batch size of 50, a learning rate of 5 × 10 -2 , a learning rate decay of 0.9 every 10 000 examples. We compare the dense neural network with a Deep diagonal-circulant ReLU networks with several factors. We use the initialization proposed in Moczulski et al. (2015) . Results Table 4 .1 shows the loss of the dense architecture versus the Deep diagonal-circulant ReLU networks with different factors. The table also shows the compression rate obtain with the Deep diagonalcirculant ReLU networks. We notice that the Deep diagonal-circulant ReLU networks manage to achieve more than 90% compression rate with a substantial loss in accuracy with factor up to 16. Adding factors improve the accuracy but make the convergence difficult. We were note able to train a model with more than 32 layers. A solution would be to use the circulant-diagonal ReLU decomposition only on certain layer in order to trade-off compression with accuracy more precisely.

#

4.2. DEEP DIAGONAL-CIRCULANT RELU NETWORKS FOR LARGE-SCALE VIDEO CLASSIFICATION:

In this section, we demonstrate the applicability of diagonal-circulant ReLU networks in the context of a large scale video classification architecture trained on the Youtube-8M dataset. Our architecture is based on a state-of-the-art architecture that was initially proposed by Abu-El-Haija et al. (2016b) and later improved by Miech et al. (2017) .

4.2.1. EXPERIMENTAL SETTINGS:

Dataset The dataset is composed of an embedding (each video and audio frames are represented by a vector of respectively 1024 and 128) of video and audio frames extracted every 1 seconds with up to 300 frames per video.

Model Architecture This architecture can be decomposed into three blocks of layers, as illustrated in Figure 4 .1. The first block of layers, composed of the Deep Bag-of-Frames embedding, is meant to make an embedding of these frames in order to make a simple representation of each video. The first block of layers, composed of the Deep Bag-of-Frames embedding, is meant to process audio and video frames independently. The DBoF layer computes two embeddings: one for the audio and one for the video. In the next paragraph, we will only focus on the describing the video embedding. (The audio embedding is computed in a very similar way.) A second block of layers reduces the dimensionality of the output of the embedding and merges the resulting output with a concatenation operation. Finally, the classification block uses a combination of Mixtures-of-Experts (MoE) Jordan & Jacobs (1993) ; Abu-El-Haija et al. (2016a) and Context Gating Miech et al. (2017) to calculate the final probabilities.

Embedding:

Experiment We want to compare the effect on the circulant-diagonal ReLU decomposition only on certain layer to evaluate the trade-off between compression rate and accuracy. First, we train the architecture presented in Figure 4 .1 without any circulant matrices to serve as a baseline. Then, we used the circulantdiagonal decomposition on each layer independently.

Hyper-parameters All our experiments are developed with TensorFlow Framework Abadi et al. (2015) . We trained our models with the CrossEntropy loss and used Adam optimizer with a 0.0002 learning rate and a 0.8 exponential decay every 4 million examples. We used a fully connected layer of size 8192 for the video DBoF and 4096 for the audio. The fully connected layers used for dimensionality reduction have a size of 512 neurons. We used 4 mixtures for the MoE Layer.

Evaluation Metric We used the GAP (Global Average Precision), as used in Abu- El-Haija et al. (2016b) , to compare our experiments.

4.2.2. RESULTS:

This series of experiments aims at understanding the effect of circulant-diagonal ReLU decomposition over different layers with 1 factors. Table 2 shows the result in terms of number of weights, size of the model (MB) and GAP. We also compute the compression ratio with respect to the dense model. The compact fully connected layer achieves a compression rate of 9.5 while having a very similar performance, whereas the compact DBoF and MoE achieve a higher compression rate at the expense of accuracy. Figure 4 .2 shows that the model with a compact FC converges faster than the dense model. The model with a compact DBoF shows a big variance over the validation GAP which can be associated with a difficulty to train. The model with a compact MoE is more stable but at the expense of its performance. 

Baseline:



6. SUPPLEMENTAL MATERIAL: TECHNICAL LEMMAS AND PROOFS:

Lemma 1. Let A l , . . . A 1 ∈ C n×n , b ∈ C n and let X ⊂ R n be a compact set. There exists β l . . . β 1 ∈ C n such that for all x ∈ X we have f A l ,β l • . . . • f A1,β1 (x) = ReLU (A l A l-1 . . . A 1 x + b). Proof. of lemma 1. Define Ω = max x∈X ,j∈[l] j k=1 A k x ∞ . Define h j (x) = A j x + β j . Let β 1 = Ω1 n

where 1 n is the n-vector of ones. Clearly, for all x ∈ X we have h 1 (x) ≥ 0, so ReLU • h 1 (x) = h 1 (x).

More generally, for all j < n -1 define β j+1 = 1 n Ω -A j+1 β j . It is easy to see that for all j < n we have h j • . . . • h 1 (x) = A j A j-1 . . . A 1 x + 1 n Ω. This garantees that for all j < n, h j • . . .

• h 1 (x) = ReLU •h j •. . .•ReLU •h 1 (x). Finally, define β l = b-A l β l-1 . We have, ReLU •h l •. . .•ReLU •h 1 (x) = ReLU (A j . . . A 1 x + b). Proof. of proposition 2. Assume N = f A l ,b l •. . .•f A1,b1

. By theorem 1, for any > 0, any matrix A i , there exists a sequence of 2n-1 matrices C

i,n D i,n-1 C i,n-1 . . . D i,1 C i,1 such that n-1 j=0 D i,n-j C i,n-j -A i <

, where D i,1 is the identity matrix. By lemma 1, we know that there exists

{β ij } i∈[l],j∈[n] such that for all i ∈ [l], f DinCin,βin • . . . • f Di1Ci1,βi1 (x) = ReLU (D in C in . . . C i1 x + b i ).

Now if tends to zero, f DinCin,βin • . . . • f Di1Ci1,βi1 -ReLU (A i x + b i ) will also tend to zero for any x ∈ X , because the ReLU function is continuous and X is compact. Let N = f D1nC1n,β1n •. . .•f Di1Ci1,βi1 . Again, because all functions are continuous, for all x ∈ X , N (x) -N (x) tends to zero as tends to zero.

Proposition 5. Let A ∈ C n×n a matrix of rank k. Assume that n can be divided by k. For any > 0, there exists a sequence of 4k + 1 matrices B 1 , . . . , B 4k+1 , where B i is a circulant matrix if i is odd, and a diagonal matrix otherwise, such that

A - 4k+1 i=1 B i F <

Proof. of proposition 5. Let U ΣV T be the SVD decomposition of M where U, V and Σ are n × n matrices. Because M is of rank k, the last n-k columns of U and V are null. In the following, we will first decompose U into a product of matrices W RO, where R and O are respectively circulant and diagonal matrices, and W is a matrix which will be further decomposed into a product of diagonal and circulant matrices. Then, we will apply the same decomposition technique to V . Ultimately, we will get a product of 4k + 2 matrices alternatively diagonal and circulant.

Let R = circ(r 1 . . . r n ). Let O be a n × n diagonal matrix where O i,i = 1 if i ≤ k and 0 otherwise. The k first columns of the product RO will be equal to that of R, and the n -k last colomns of RO will be zeros. For example, if k = 2, we have: We want to find the values of d ij such that W RO = U . We can formulate this as linear equation system. In case k = 2, we get:

RO =        r 1 r n 0 • • • 0 r 2 r 1

:

In network such as AlexNet, the last 3 fully connected layers use 58M out of the 62M total trainable parameters.

http://scikit-learn.org/stable/modules/generated/sklearn.datasets.make classification.html

Figures and Tables:

Bounded depth Deep diagonal-circulant ReLU networks are universal approximators on any compact set X . Proof. Proposition 2 shows that bounded-width Deep diagonal-circulant ReLU networks can approximate any Deep ReLU network. It has been shown recently in Hanin (2017) that bounded-width deep ReLU networks are universal approximators. Together, these two results concludes the proof.It is important to remark that Deep diagonal-circulant ReLU networks are not necessarily more compact than Deep ReLU networks. Indeed, consider a n-wide Deep ReLU network with l layers having ln 2 weights. The previous corollary tells us that this network can be decomposed in a Deep ReLU networks involving l(2n-1) matrices, i.e. 2ln(2n -1) weights.Despite the lack of theoretical guarantees a number of work provided empirical evidence that bounded width and small depth Deep diagonal-circulant ReLU networks result in good performance (e.g.Moczulski et al. (2015);Araujo et al. (2018);Cheng et al. (

Figure 4.1: This figure shows the architecture used for the training of the YouTube-8M dataset.

Let us define k diagonal matricesD i = diag(d i1 . . . d in ) for i ∈ [k].For now, the values of d ij are unknown, but we will show how to compute them. Let W = k i=1 D i S i-1 . Note that the n -k last columns of the product W RO will be zeros. For example, with k = 2, we have:11 + r n d 21 r n d 11 + r n-1 d 21 0 • • • 0 r 2 d 12 + r 1 d 22 r 1 d 12 + r n d 22 . 1n + r n-1 d 2n r n-1 d 1n + r n-2 d 2n 0 • • • 0

This table shows the loss obtain on the synthetic dataset given the number of factor used for each layer.

Table content: <table><tr><td>Factors</td><td>#Params</td><td>Compress. Rate (%)</td><td>Loss</td></tr><tr><td>Dense</td><td>2 107 397</td><td>-</td><td>0.16016</td></tr><tr><td>k = 2</td><td>19 461</td><td>99.0</td><td>0.38847</td></tr><tr><td>k = 4</td><td>35 845</td><td>98.2</td><td>0.36668</td></tr><tr><td>k = 8</td><td>68 613</td><td>96.7</td><td>0.33275</td></tr><tr><td>k = 16</td><td>134 149</td><td>93.6</td><td>0.32798</td></tr><tr><td>k = 32</td><td>523 269</td><td>75.1</td><td>0.32657</td></tr></table>

This table shows the effect of circulant-diagonal decomposition on different layers. this paper we provided a theoretical study of the properties of Deep diagonal-circulant ReLU networks and demonstrated that they are bounded width universal approximators. The bound on this decomposition allowed us to calculate the error bound on any Deep diagonal-circulant ReLU networks given the depth on the network and the singular values associated with the weight matrices. Our empirical study demonstrate that we can trade-off model size for accuracy in accordance with the theory, and that we can use Deep diagonal-circulant ReLU networks in large scale machine learning applications.

Table content: <table><tr><td>Model</td><td/><td colspan="2">#Weights</td><td colspan="2">Size (MB)</td><td colspan="3">Compress. Rate (%)</td><td>GAP@20</td><td>Diff.</td></tr><tr><td>Dense Model</td><td colspan="3">45 359 764</td><td/><td>173</td><td/><td>-</td><td/><td>0.846</td><td>-</td></tr><tr><td>Compact DBoF</td><td colspan="3">36 987 540</td><td/><td>141</td><td/><td>18.4</td><td/><td>0.838</td><td>-0.008</td></tr><tr><td>Compact FC</td><td colspan="3">41 181 844</td><td/><td>157</td><td/><td>9.2</td><td/><td>0.845</td><td>-0.001</td></tr><tr><td>Compact MoE</td><td colspan="3">12 668 504</td><td/><td>48</td><td/><td>72.0</td><td/><td>0.805</td><td>-0.041</td></tr><tr><td/><td/><td/><td/><td colspan="5">Comparison of the effect of compactness over</td></tr><tr><td/><td/><td/><td/><td colspan="5">different layers with the base model</td></tr><tr><td/><td/><td>0.87</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>0.86</td><td colspan="2">Dense Model</td><td/><td colspan="3">Model with compact DBoF</td></tr><tr><td/><td/><td>0.85</td><td colspan="3">Model with compact FC</td><td colspan="3">Model with compact MoE</td></tr><tr><td/><td>Validation GAP</td><td>0.8 0.81 0.82 0.83 0.84</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>0.79</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>0.78</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>0.77</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td></tr><tr><td/><td/><td/><td/><td/><td/><td>Epochs</td><td/><td/></tr><tr><td colspan="10">Figure 4.2: Validation GAP according to the number of epochs for different compact models.</td></tr><tr><td colspan="2">5 CONCLUSIONS</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 The paper proposes using structured matrices, specifically circulant and diagonal matrices, to speed up computation and reduce memory requirements in NNs. The idea has been previously explored by a number of papers, as described in the introduction and related work. The main contribution of the paper is to do some theoretical analysis, which is interesting but of uncertain impact. The experiments compare performance against DeepBagOf`Fframes (DBOF) and MixturesOfExperts (MOE). However, there are other algorithms that are both more competitive and more closely related. I would like to see head-to-head comparisons with tensor-based algorithms such as Novikov et al: https://papers.nips.cc/paper/5787-tensorizing-neural-networks, which achieves huge compression ratios (~200 000x), and other linear-algebra based approaches. AFTER READING REBUTTAL I*ve increased my score because the authors point out previous work comparing their decomposition and tensortrains (although note the comparisons in Moczulski are on different networks and thus hard to interpret) and make a reasonable case that their work contributes to improve understanding of why circulant networks are effective. I strongly agree with authors when they state: "We also believe that this paper brings results with a larger scope than the specific problem of designing compact neural networks. Circulant matrices deserve a particular attention in deep learning because of their strong ties with convolutions: a circulant matrix operator is equivalent to the convolution operator with circular paddings". I would broaden the topic to structured linear algebra more generally. I hope to someday see a comprehensive investigation of the topic.