Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Summary
The authors introduce kaleidoscope matrices (K-matrices) and propose to use them as a substitute for structured matrices arising in ML applications (e.g. circulant matrix used for the convolution operation). The authors prove that K-matrices are expressive enough to capture any structured matrix with near-optimal space and matvec time complexity. The authors demonstrate that learnable K-matrices achieve similar metrics compared to hand-crafted features on speech processing and computer vision tasks, can learn from permuted images, achieve performance close to a CNN trained on unpermuted images and demonstrate the improvement of inference speed of a transformer-based architecture for a machine translation task.

		
Review
The overall quality of the paper is high. The main contribution of the paper is the introduction of a family of matrices called kaleidoscope matrices (or K-matrices) which can be represented as a product of block-diagonal matrices of a special structure. Because of the special structure, the family allows near-optimal time matvec operations with near-optimal space complexity for structured matrices which are commonly used in deep architectures. 

The proposed approach is novel. It gives a new characterization of sparse matrices with optimal space complexity up to a logarithmic term. Moreover, the proposed characterization is able to learn any structured matrix and matvec time complexity of the K-matrix representation is near-optimal matvec time complexity of the structured matrix. Even though in the worst-case complexity is not optimal, the authors argue that for matrices that are commonly used in machine learning architectures (e.g. circulant matrix in a convolution layer) the characterization is optimal. This results in a new differentiable layer based on a K-matrix that can be trained with the rest of an architecture using standard stochastic gradient methods. However, it is worth noting that the reviewer is not an expert in the field, and it is hard for him to compare the proposed approach with previous work.
						
The paper is generally easy to follow. Even though the introduction of K-matrices requires a lot of definitions, they are presented clearly and Figure 1 helps to understand the concept of K-matrices. The experimental pipeline is also clear.

Given the special structure of the family, the reviewer might guess that having K-matrices can slow down the training, i.e. it might require more epochs to achieve the reported results compared to baselines. Providing training plots might increase the quality of the paper.

The experimental results are convincing. First, the authors show that K-matrices can be used instead of a handcrafted MFSC featurization in an LSTM-based architecture on the TIMIT speech recognition benchmark with only a 0.4% loss of phoneme error rate. Then, the authors evaluate K-matrices on ImageNet dataset. In order to do so, they compare a lightweight ShuffleNet architecture which uses a handcrafted permutation layer to the same architecture but with a learnable K-matrix instead of the permutation layer. The authors demonstrate the 5% improvement of accuracy over the ShuffleNet with 0.46M parameters with only 0.05M additional parameters of the K-matrix and the 1.2% improvement of accuracy over the ShuffleNet with 2.5M parameters with only 0.2M additional parameters of the K-matrix. Next, the authors show that K-matrices can be used to train permutations in image classification domains. In order to demonstrate so, they take the Permuted CIFAR-10 dataset and ResNet-18 architecture, insert a trainable K-matrix at the beginning of the architecture and compare against ResNet-18 with an inserted FC-layer (attempting to learn the permutation as well) and ResNet-18 trained on the original, unpermuted CIFAR-10 dataset. With K-matrix, the authors achieve a 7.9% accuracy improvement over FC+ResNet-18 and only a 2.4% accuracy drop compared to ResNet-18 trained on the original CIFAR-10. Finally, the authors demonstrate that K-matrices can be used instead of the decoder’s linear layers in a Transformer-based architecture on the IWSLT-14 German-English translation benchmark which allows obtaining 30% speedup of the inference using a model with 25% fewer parameters with 1.0 drop of BLEU score.

Overall, the analysis and the empirical evaluations suggest that K-matrices can be a practical tool in modern deep architectures with a variety of potential benefits and tradeoffs between a number of parameters, inference speed and accuracy, and ability to learn complex structures (e.g. permutations).


Improvements
1. Even though K-matrices are aimed at structured matrices, it would be curious either to empirically compare K-matrices to linear transformations in fully-connected networks (i.e. dense matrices) or to provide some theoretical analysis.
2. Section 3.3 argues that K-matrices allow to obtain an improvement of inference speed, however, providing the results of convergence speed (e.g. training plots with a number of epochs) will allow a better understanding of the proposed approach and will improve the quality of the paper.
review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: This paper introduces a structured drop-in replacement for linear layers in a neural network, referred to as Kaleidoscope matrices. The class of such matrices are proven to be highly expressive and includes a very general class of sparse matrices, including convolution, Fastfood, and permutation matrices. Experiments are carried in a variety of settings: (i) can nearly replace a series of hand-designed feature extractor, (ii) can perform better than fixed permutation matrices (though parameter count also increased by 10%), (iii) can learn permutations, and (iv) can help reduce parameter count and increase inference speed with a small performance degradation of 1.0 BLEU on machine translation.

This appears to be a solid contribution in terms of both theory and practical use. As I have not thought much about expressiveness in terms of arithmetic circuits (though I was unable to fully follow or appreciate the derivations, the explanations all seem reasonable), my main comments are regarding experiments. Though there are experiments in different domains, each could benefit from some additional ablations, especially to existing parameterizations of structured matrices such as Fastfood, ACDC, and any of the multiple works on permutation matrices and/or orthogonal matrices. Though Kaleidoscope include these as special cases, it is not clear whether when given the same resources (either memory or computational cost), Kaleidoscope would outperform them. There is also a matter of ease of training compared to existing approximations or relaxations, e.g. Gumbel-Sinkhorn.

Pros:
 - The writing is easy to follow and concise, with contributions and place in the literature clearly stated. 
 - The Kaleidoscope matrix seem generally applicable, both proven theoretically and shown empirically (experiments are spread across a wide range of domains). 
 - The code includes specific C++ and CUDA kernels for computing K matrices, which will be very useful for adaptation.
 - The reasoning using arithmetic circuits seems interesting, and the Appendix includes a primer.

Cons:
 - For the squeezenet and latent permutation experiments, would be nice if there is a comparison to other parameterizations of permutation matrices, e.g. gumbel-sinkhorn.
 - For the speed processing experiment, did you test what the performance would be if K matrix is replaced by a fully connected layer? This comparison appears in other experiments, but seems to be missing here for some reason. It would lead to better understanding than only comparing to SincNet.
 - The setup for the learning to permute experiment is not as general as it would imply in the main text. The matrices are constrained so that an actual permutation matrix is always sampled, and the permutation is (had to be?) pretrained to reduce total variation for 100 epochs before jointly trained with the classifier. Though this is stated very clearly in the Appendix, I hope the authors can also communicate this clearly in the main text as it appears to be a crucial component of the experimental setup.

Comments:
 - How easy is it to train with K matrices? Did you have to change optimizer hyperparameter compared to existing baselines? 
 - There seems to be some blurring between the meaning of structure (used to motivate K matrices in the introduction) and sparsity (used to analyze K matrices). Structure might also include parameter sharing, orthogonality, and maybe other concepts. For instance, while Kaleidoscope matrices might include the subclass of circulant matrices, can they also capture the same properties or "inductive bias" (for lack of better word) as convolutional layers when trained?
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The authors propose learnable "kaleidoscope matrices" (K-matrices) in place of manually engineered structured and sparse matrices. By capturing "all" structured matrices in a way that can be learned, and without imposing a specific structure or sparsity pattern, these K-matrices can improve on existing systems by 
* capturing more structure (that was not handled by the existing manually engineered architecture),
* running faster than dense implementations.

The claim that "all" structured matrices can be represented efficiently is a strong one, and in section 2.3 the authors make it clear what they mean by this. Although the proof is long and beyond the expertise of this reviewer, the basic explanation given in section 2.3 makes their point clear for the non-expert reader.

The balance of the paper empirically tests the claims of learnable structure and efficiency.

On the basis that these experiments essentially bear out the claims of the paper, I selected to accept the paper.

Weaknesses:

1. Regarding the ISWLT translation task result:
With this dataset, it's a bit of a stretch to say there was "only a 1 point drop in BLEU score". That's a significant drop, and in fact the DynamicConv paper goes to significant lengths to make a smaller 0.8 point improvement. There are probably many other ways to trade BLEU score for efficiency, and without showing those other methods (and the point drops they have), it's not clear that K-matrices are a good way to speed up decoding a bit.




review_title: Official Blind Review #3

Meta-review: The paper generalizes several existing results for structured linear transformations in the form of K-matrices. This is an excellent paper and all reviewers confirmed that.
Decision: Accept (Spotlight)