Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

The 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. 

The 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.

Finally, 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. 

As 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. 


review_title: The paper studies the idea of butterfly networks, drawing inspiration from the sketching literature.

final_score: rating: 7: Good paper, accept
review_content: 
The paper provides an interesting and novel use of butterfly factoziations in encoder-decoder networks. Specifically, the paper proposes replacing the 
encoder 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.

######

I 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. 

######

pros 
+ The proposed truncated butterfly network is novel. Aside from the algorithmic contribution, the theorem in the paper raise important questions about
the optimization landscape of butterfly networks. 
+ The paper is clearly written and well justified 
+ Exhaustive literature survey and background on relevant work in both the matrix factorization and neural networks front

######

cons 
- 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 
the 2019 paper but the details on how Indyk et al train their network are lacking without looking up the original paper. 

- 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.   

######

questions: see the above section 
review_title: Interesting paper

final_score: rating: 5: Marginally below acceptance threshold
review_content: I list the strong and weak points in the following:

### Strong points

- 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. 


### Weak points

- 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.

- 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? 

- 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?

- 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. 

- 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?
review_title: Motivated by Johnson-Lindenstrauss-type results, this paper proposes to replace a dense linear layer in any neural network by a composition of two truncated butterfly networks and a smaller dense layer in between. Theoretical result is given for the two-layer encoder-decoder network where the encoder is replaced by one truncated butterfly network and a dense layer. Empirical results are given for several synthetic  and real datasets.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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:
-	When 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? 
-	In 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?
-	For 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.
-	Theorem 1: What is Omega in the exponent? I couldn’t find its definition.
-	Figure 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).
-	 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.
-	Figure 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).
-	Figure 1(b): Please extend the plots beyond epoch 20 to see how the values are stabilized for the four methods.
-	Quality of Figures, for example Fig 3, must be improved (too small fonts, blurred, etc.)
review_title: Further details on experimental setting are required

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