Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper explores learning more general neural architectures by leveraging a novel, continuous parameterization of architecture (based on kaleidoscope marix) and one-shot style NAS algorithms. They present results on standard, and permuted cifar10, then 3 more exotic datasets including PDE solutions, problems from protein folding, and music modeling.
main_review: This seems like a solid paper. I would advocate for accepting though I am not an expert in this field (hence my low confidence). My rational for a 6 vs 7 is the limited baselines comparing to existing NAS methods.

Clarity: My main concern is about clarity of the presentation. I found the the abstract discussion based solely on equations of this method difficult to follow. I realize the paper is space constrained, but including examples of K-matrix / even showing how standard operations map into XD-operators would be greatly appreciated. The description of the method also takes around 5-6 pages as well which feels very long.

Results: 
I found these experiments quite compelling. Having baselines that outperform existing work is always great!

For the PDE, protein and music, it would be interesting to see another NAS comparison -- in particular a discrete search space style NAS algorithm like what was done in the cifar10 experiments.

One question I have is about how useful the resulting architectures are. In Darts, one can discretize the discrete search space resulting in very efficient architectures for future tasks. In this work, this doesn't seem so straight forward (and it is even stated that this was not done on purpose). Do the K-matrix style formulation lead to an efficient formula? Naively it seems like without it it would be up to 10x more costly (judging by the resnet-20 cifar10 walltimes).

Related, but do you have any understanding of what kinds of "architectures" these things learn? Is anything interpretable?





limitations_and_societal_impact: Some limitations are discussed, but as noted above I would appreciate some discussion on inference costs / how to actually use these models / some notion of overhead at inference time.

No societal impact is discussed.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The core contribution of this work is to re-image of NAS operation spaces to include both standard operations as well as new operations. This work replaces the Discrete Fourier Transform (DFT) in the diagonal decomposition by a more expressive family of efficient liner transforms known as Kaleidoscope or K-matrices (Expressive Diagonalization Operations), which comprises of a large search space of various types of grid-based convolutions and pooling, permutations, graph convolutions, the Fourier Neural Operator, and more. This work developed a simple procedure which transforms any backbone convolutional neural network into an architecture search space by replacing its operations with XD-operations. This space is then searched using a simple weight-sharing algorithm. This work yields models that are 15% more accurate than standard discrete search spaces on permuted CIFAR-10, highlighting the fragility of standard NAS operation spaces on new datasets, and thus the need for XD-operations.
main_review: This work brings up an interesting perspective that ,. This work also proposes to replace matrices F and F-1 in by any one of a general family of efficient matrices, which yields the single-channel version of expressive diagonalization operations. 

Strengths:
1. This approach in general provides a much more expressive search space for NAS, by devising XD-opeartions with K-matrix architecture parameters.
2. The formulation and complexity analysis on a single-channel XD-operations with K-matrix architecture parameters is pretty clear. 

Weakness:
1. The paper is not clear about how to rank models or evaluate models generated from this enlarged search space. The reviewer is particularly confused by "Note that the fully continuous nature of XD-operations means that we will only evaluate the final network returned by search". 

2. Empirical results are weak. Only Cifar10 results are provided and only bad baselines (LeNet and ResNet-20) are compared against. Also, it is odd that "On CIFAR-10 we do not expect to see much improvement from XD-operations over the CNN backbone used to initialize search, as convolutions are already the “right” operation for images", why this work should evaluate on CIFAR10 then?

5. Application section is interesting but not very formal.  There isn't any standard benchmarks used or any well-known baselines are compared upon. 

Overall, the reviewer thinks the general direction is interesting, however, evaluation is poor. The work is not thoroughly evaluated and no strong baselines are provided. 

limitations_and_societal_impact: Yes, both are addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper starts by introducing Kaleidoscope-matrices (K-matrices). The core idea here is: 
1. Most of the interesting operations in NAS spaces are linear and can be expressed as a matrix multiplication $A_W x$
2. The operations can therefore be diagonalized by a DFT
3. We can factorize the DFT matrices into “butterfly matrices” (such that, for a factorization of factor $N$, we can write $F =$ the product of the $N$ butterfly matrices and a permutation matrix). 
4. By allowing this factor $N$ to vary, the matrix multiplication $A_W x$ can be generalized to express a wider family of operations 

The core contribution of this paper appears to be using K-matrices in a NAS setting (which involves a reasonable amount of work):
- The architecture parameters are continuous 
- K-matrices can’t express parameter-free ops
- Finding/evaluating new operations in a NAS setting

Their NAS process then looks like:
1. Take in a backbone and generalize it to a supernet 
2. Simultaneously train the architecture parameters and the weights 
3. Extract a net + weights for inference

The paper then explores a few unusual tasks and shows that this generalization process is worthwhile. 

main_review: Overall this paper was a joy to read, filled with insightful interpretations of things I previously thought boring (e.g. the definition of NAS spaces as a set of operations with the same W,X,Y and their expressibility). The paper would be strengthened by more thorough empirical results, but I understand why in this particular setting that could hard to provide.

The paper has a hard task: construct a general framework for neural architecture search that will let us do more exciting things than squeeze out performance on existing benchmarks, but that also doesn’t perform drastically worse than existing (extremely heavily engineered) techniques on said benchmarks. 

I think the authors do a good job of showing the expressivity of their method with regards to diverse tasks while also showing that it continues to work on the more boring tasks (e.g. CIFAR-10). Even so, I do think the lack of focus on the typical “NAS-bench” setups is a little disappointing. I would have liked to see what happened if the authors took a NAS-bench cell/skeleton as their starting point — since we have results for a wide range of NAS-techniques on those benchmarks, it would be easier to put their method in context.

The authors perform some analysis of the Euclidean distance between their architecture parameters (which I’m assuming is butterfly factors + bias?) and the traditional convolution operation show that they can tailor then operations to suit the complexity of the tasks, which is very nice. 

The authors then dive into a few diverse tasks, none of which I have experience with so may have missed some evaluation points:

**Solving PDEs**: this section is neat, and it shows that the XD-operations can be used to replace the hand-engineering effort that went into designing Fourier Neural Operators. I may have missed it but it would be good to have some detail on the dataset specifically (number of training/test samples per PDE/resolution/viscosity). My immediate concern is that learning over a space of operations like this probably requires a lot of data? 

**Protein folding distance prediction**: I don’t know much about this task but the results seem good (there are minor improvements over both ResNet and Dilated ResNet at each depth). 

**Music modeling**: again, I don’t know much about the task but the results seem good.

I’m happy that the evidence provided is sufficient to show that this process can be used to take a backbone, generalize it to some family of ops, and then specialize the operations to suit the task. That alone is a very useful contribution. 

In the abstract the authors state “Starting with any standard backbone such as ResNet, we show how to transform it into a search space over XD-operations and how to traverse the space using a simple weight-sharing scheme.” My assumption from this sentence was that they would use is a single backbone used for all three of the tasks. That they don’t suggests that though the method provides a good level of generalization, it still requires some hand engineering to get it to work well.

## Overview

**Originality**: In some ways this felt like the inevitable next step to [1]. However, it appears there is still a reasonable amount of novelty/originality to the paper in getting K-matrices to work for NAS. Related work is adequately cited.

**Quality**: The submission is technically sound, and filled with satisfying definitions of the various aspects of the problem. The authors show the performance of their method on three unusual problems, plus the more classic task of CIFAR-10. The step from CIFAR $\rightarrow$ permuted CIFAR $\rightarrow$ other tasks is a nice logical narrative. The experimental evidence isn't overwhelmingly strong, but the paper does break NAS into relatively new territory so I don't think a huge amount of empirical evaluation is needed.

**Clarity**: The submission is very clearly written, organized, and thoroughly cites background material which was useful for me as a reader with not a great deal of knowledge regarding butterfly matrices and the related work. It's an interesting topic because the paper is trying to generate new types of operation which by their nature probably won't be particularly intuitive, but I feel like the authors did a good job of showing why a few example operations are expressible in their search space.

**Significance**: The paper addresses a major limitation with neural architecture search: that we typically only use a very restrictive set of operations that we know to work well on a limited range of tasks. I'm not convinced that after this paper, everybody in the NAS subfield will switch to using K-matrices, but it seems like a useful tool in the toolbox for people who are using NAS outside of CIFAR-10. 

## Questions

1. I’m a little confused about exactly what the “architecture parameters” look like. Is it a collection of “butterfly factors” and biases for K, L, and M? Are all of the cells in the network the same or do you have different architecture parameters for each layer? 
2. In my interpretation, the authors are almost implicitly proposing a new “NAS-bench” which is composed of XD-operations (a much wider family of operations than what we currently use). To that end, it would be nice to see some statistics about what the space of XD-operations looks like: if you randomly sample from the space, how much variance is there in the performance of the operations? Is the space dense with very-convolution-like operations or is it quite uniformly distributed? What happens if you take the cell-structure/backbone from NATS-bench/ NAS-Bench-101/ NAS-Bench-201 and set all of the operations to be XD-operations? 
3. On page 6 the authors state “On CIFAR-10 we do not expect to see much improvement from XD-operations over the CNN backbone used to initialize search, as convolutions are already the “right” operation for images.” I guess this is true, but I was wondering whether the authors think there is any scope to improve on convolution using their method in future? Given the volume of work on convolutional-alternatives (LambdaNetworks, the Shift operation, OctaveConvolution etc.) for image domains, I was hoping that within a space of XD-Operations we might find more of these.
4. One thing I can’t quite figure out is whether all of the operations expressible in the space of XD-Operations are reduced forms of convolution (e.g. adding dilation)?  Could you express something like transposed convolution? Is there anything expressible as an XD-Operation that isn’t expressible as unstructured pruning in the matrix A? 
5. An evaluation of the limitations of the expressivity of the search space would also be nice. For example, I assume you probably can’t express something like a self-attention layer due to the softmax? 

[1] Dao, Tri, et al. "Kaleidoscope: An efficient, learnable representation for all structured linear maps." arXiv preprint arXiv:2012.14966 (2020).

limitations_and_societal_impact: The authors addressed the potential negative societal impact of their work.

In general, moving NAS away from vision and language tasks is a direction that we should probably encourage.
review_title: null

Meta-review: This work is a well-presented and motivated perspective on NAS, where a reparameterisation of the search space using K-matrices yields a method that is able to operate across a number of interesting domains. The only major concern raised by the reviewers is, naturally, the choice of domains. The reviewers all agreed the authors have selected a diverse range of tasks and demonstrated their method on each. Naturally, given this demonstration, there is some anticipation of demonstrating this method on a diverse set of larger-scale problems, perhaps this will be future work.
Decision: Accept (Poster)