Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper claims to perform neural operator search on a search space defined by a family of Kaleidoscope operations. The paper address the computation challenges in the search using  a supernet, and performs variable ablation studies to show that the searched K-Op can slightly outperforms existing convolution operators.

Here I appreciate if the authors can clarify the following points:

a) "Each butterfly matrix of dimension n x n is itself a product of log n sparse matrices with a special fixed sparsity pattern, which encodes the recursive divide-and-conquer algorithms such as the FFT."

Here the author deliberately selects a family of operations that contains FFT and convolution. It is unclear how you constrain the search space of K-matrices; I get you searched K operations, but I did not find it's structure and how does that different from FFT. I'm also confused about the point of fig.2, what's the point you want to say about these feature map?

b) Ablation studies.

There are a lot of ablation studies show that the searched K-operations are better than convolution. However, none of them show they actually pushed SoTA results. Considering the fact that there are so many tricks (https://github.com/facebookresearch/LaMCTS/tree/master/LaNAS/LaNet) in boosting the performance of a CNN, it is more convincing to see the searched K operators can actually push the boundary. The ablation studies in the current experiments are not enough to convince me, especially they are focusing on relatively simple tasks, e.g. CIFAR-10, MNIST.

c) Another thought, Tensorized Neural Network has also tried to replace of current operators, and their hyper-parameters can also formulate a search space; My main concern about this line of work is "are we really making progress here"?

Here we're building something based one prior knowledge; if we will end up someting similar to convolution, so what's the point of doing it? However, the paper lacks a strong evidence that they invented a new operators that actually work. This is my main concern of this paper.





review_title: An interesting paper

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

The paper introduces Kaleidoscope-operations to reprameterize convolutions. The reparameterization results in a more general search space of convolutions. Moreover, it enables one-level optimization on the convolution search as well as a supernet optimization, which avoids post-search discretization and post-discretization re-training.  


Pros:

The paper seems a good reading material to teach readers about a big picture of convolution search problem or even neural architecture search problem.

The paper also shows a huge ambitious motivation to touch the boundary of the current main-stream NAS methodologies. 

The idea of introducing repratermeterized convolutions (i.e., K-operations that was originally proposed by Dao et al., 2020) to convolution search seems novel and promising to me. 

The evaluation is comprehensively conducted on several novel search spaces over vision and text data, and the results show the effectiveness of the proposed method. When being evaluated on permuted CIFAR and spherical MNIST, the new method shows some superiorities.


Cons:

It seems that the proposed model is designed to merely search for convolutions with a reprameterization approach (i.e, K-operation). Compared to regular NAS algorithms like DARTS that search for a much larger architecture space including convolutions, poolings, skip connections, this paper’s search space is merely on reprameterized convolutions. This makes me disappointed as both the title and the beginning parts somehow mislead readers that the paper aims at making a good innovation in the big scope of NAS. However, I finally realize that it actually searches for better convolutions rather than an entire neural architecture, after I went to the last paragraph of Page 5. Moreover, the search merely on convolutions is very likely to result in a much easier neural architecture optimization task, and make the so-called supernet (without post-search discretization & post-discretization retraining) work. This also reminds me that there exists one work [Stamoulis et al., 2019] which shares a similar motivation with this submission. In particular, [Stamoulis et al., 2019] proposes one single-path over-parameterized ConvNet to encode all architectural decisions with  convolutional kernel parameters. The overall network loss is directly a function of the “superkernel” weights, where the learnable kernel- and expansion ratio-related parameters can be directly derived as a function of the kernel weights. This strategy also enables one-level optimization and has a potential for supernet optimization as suggested by the submission. 


[Stamoulis et al., 2019] Single-path NAS: Designing hardware-efficient convnets in less than 4 hours. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2019.


In Table 1, I find the best performances on CIFAR-10 and the transferring to CIFAR-100 are still far away from the state of the art. For example, DARTS (Liu et al., 2019) can obtain about 97% and 74% accuracies on CIFAR-10 and CIFAR-100 respectively. Please explain which causes this gap. For a fair comparison, I see the results of the proposed K-op with supernet SGD/SGDR are worse than Conv (fixed operation baselines, offline), while they are better when warm starting with convolution. What if warm-start is also applied to Conv (fixed operation baselines, offline)? 

As presented in the paper, Fig.2 shows that learned K-operations use more global information to extract features. But what is the benefit for deep learning?


Table 2 is not self-contained. It should clarify the meaning of CR, MPQA, …, TREC in the caption. I guess they are the 7 used datasets according to the presentation in the main text. Again, I find the proposed method can obtain better results only when using the warm-start strategy, while it generally performs worse than the competitor (i.e., convolution) when training from scratch. 

The last column of Table 4 seems confusing to me whether it corresponds to the case that uses warm start or from scratch. 

In the paragraph of “utterfLeNet: Unpermuting Image Data”, the index of the referred section is missing.

Overall I think the paper oversells the new idea and the corresponding technology. Thus I tend to suggest a major revision by tuning down its current tone throughout the paper, while I like the idea and really expect the paper can be baked better for publication. 



review_title: Official Blind Review #3

final_score: rating: 5: Marginally below acceptance threshold
review_content: # Summary

The paper proposes to search neural network operations that outperform some human-designed ones, e.g. convolution. Specifically, it proposes to extend the Kaleidoscope paper to formulate a new searchable operation. Combining with differently architecture search method, 

# Strength

The proposed Kaleidoscope Op is new to the field and seems to be an interesting aspect, searching for an operation similar to convolution but on different tasks. 

# Major weakness

## 1. The presentation of this work hinders my understanding. 

- The paper introduces a simple operation set but with many unnecessary descriptions and definitions. For example, what is the purpose to introduce definition 3.1? Does a parameterized operation return a parameterized function? This is confusing. 

- Is Section 2 necessary? It occupies a significant space in the main text but is not related to the methodology section 3. I did not see any definition introduced in this section later. Instead, the definition of the core method of Kaleidoscope operations is not well introduced. The paper keeps mentioning the Dao 2020 and K-matrices, yet it only briefly defines it. 

- What's the purpose to emphasize the three `key properties'? Will the author show some ablation study what happened if these properties are violated for some other operations? Why they are good properties in the NAS domain? 

- How do you combine the NAS with K-Op (defined in 3.2)?
It is strange to see the authors spend a large space to describe the common NAS algorithms in section 2 but do not clearly state how this K-Op is combined with the search algorithms. On page 6, there is one sentence saying `K-op comprise a continuous search space...', but what exactly is that? What are the settings of your experiments? Please correct me if I miss something. For now, it should be clearly defined instead of a brief sentence to forester the reproducibility of this method. 

- What's offline in Table 1? Does it mean you generate the architecture after search and train from scratch on CIFAR-10? But it seems on many methods the offline surpass the super-net, which is again weird. 



## Weak baselines
This paper essentially extends the original paper to make it searchable. Does it seem to be reasonable to compare against it at least over one task in the Kaleidoscope paper? The baselines, e.g. LeNet, in this work are too weak compared to the recent NAS approach. I understand this paper does not claim to be state-of-the-art but showing the potential, yet with this baseline on CIFAR-10, it is hard to compare with the literature.


# Minor issues

- a random search on NAS on Page 7, did you mean Yu et al 2020 (evaluating the search phase of NAS) instead of Yang et al. 2020 (NAS Evaluation is frustratingly hard)? The latter describes the stand-alone training pipeline can significantly impact the reproducibility where Yu et al. describes that many NAS algorithms do not even outperform the random search.

- `FFT' on page 4 not defined when first used.
Broken reference on page 8.

- Repeating descriptions: Page 2 Top `desirable properties: short description length ...` with page 4 first paragraph of section 3.


review_title: An interesting method but with flaws

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Summary:** 
The authors propose a new NAS method that comes with a space of operations generalizing the convolution. The proposed method makes it possible for users to design their own search spaces according to the training data. However, the experiments and writing should be further improved.

**Strengths:**
1. The proposed method enables users to build their own search spaces.
2. The authors incorporate Kaleidoscope-operations to develop a new search space.

**Weaknesses:**
1. The authors only conduct experiments on small datasets, e.g., CIFAR. It would be stronger to report the comparison results on ImageNet.
2. The authors seek to allow users to design their own search spaces adapted to their data, which, however, is very labor-intensive. Moreover, it is also not clear how different search spaces would affect the search performance?
3. The proposed method fixes the backbone architecture and only searches for the optimal operation. However, this method ignores the topology of architectures. In my opinion, architecture topology should be an important factor to search in NAS.
4. The authors argue that the proposed method “enables the discovery of good design patterns with limited human specification from data in under-explored domains”. What does “under-explored domain” mean? How to define it?
5. What is FFT in Page 4? There is no definition before it appears, which makes the paper hard to follow.
6. From Definition 3.2, the search process w.r.t. k-operations seems to learn the parameters of the matrix K1 and K2. Thus, it seems not a typical NAS process. It would be better to illustrate the relationship between the proposed method and the standard NAS.
7. It is not clear what the proposed search space is. How large is it?
8. Several state-of-the-art NAS methods should be compared in the experiments, such as PDARTS, PCDARTS, etc.
9. The writing of this paper should be improved. The paper is hard to follow and there are many grammatical errors:
(1) In Page 3, “the main challenge … is intractability” should be “The main challenge … is intractable”.
(2) In Page 5, “Dao et al. (2020) propose replace convolutional layers” should be “Dao et al. (2020) propose to replace convolutional layers”

review_title: The experiments and writing should be further improved

Meta-review: Motivated by the possibility of Neural Architecture Search on domains beyond computer vision, this paper introduces a new search space and search method to improve neural operators. It applies the technique to problems in vision and text.

Reviewer 1 found the paper interesting and liked the motivation of considering different tasks in NAS. However, they found some aspects of the paper confusing and, like other reviewers, thought that the baselines were weak. The authors clarified some points, and R1 said that some, but not all, concerns were resolved. The reviewer improved their score by a point but still was not in favour of acceptance.

Reviewer 2 thought the paper was interesting but questioned its main claim: that it was proposing a search space over novel operators. They argued that what was discovered was similar to convolution and therefore not much had been gained. They questioned the significance of the ablation studies: there were a lot of them, but they focused on relatively simple tasks like MNIST and CIFAR-10. They also asked some clarifying questions which were answered by the authors. Pushing back on the point about the smaller scale of the experiments (in a general reply to all reviews), the authors said that the goal of their work was not advancing computer vision, but to push NAS beyond computer vision and simple search spaces to new application domains.

Reviewer 3 liked that the paper gave a good overview of the NAS problem and thought that it was ambitious. They also thought the approach was novel and promising. Like R2’s comment, R3 seemed disappointed that the search was over “reparameterized convolutions”. In fact, they thought that the paper was overselling its contribution. They pointed out that performance was still far from state-of-the art on the various benchmarks. The authors argued against this view of “reparameterizing convolutions” and claimed that the search space was, in fact, much larger than that of DARTS. R3 read and responded to the rebuttal, appreciating the response but ultimately thought that the search space wasn’t clear and comparisons fell short.
Reviewer 4 shared similar pros & cons as have been pointed out by the other reviewers. They thought that operator search was limiting and that the paper should also consider topology. The authors responded to this, saying that they intentionally fixed the topology. Searching beyond operators was out of scope. R4 responded to the rebuttal though still had some remaining concerns both in terms of motivation and execution.

Multiple reviewers said that they would have considered the paper more favourably had an updated paper been submitted, addressing some of the original concerns. As it stands, all of the reviewers think that the paper has some merits but none believe after considering the author response, that the paper is ready for acceptance. I see no reason to overrule the consensus.
Decision: Reject