Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars

Summary

In this paper, the authors focus on the search space issue in neural architecture search and propose a unifying search space design framework that models all candidate neural structures with context-free grammars. This approach enlarges the search space, which is more likely to find high-performance architectures, and meanwhile does not bring much search cost with the proposed Bayesian Optimization for hierarchical NAS. Experimental results show that systems with hierarchical search spaces outperform the previous NAS systems.

Strengths

1. The issue that this article focuses on is precious. The search space is an important issue for NAS, and somewhat determines the upper bound of performance of the resulting system. The limited search space will make the system difficult to find a proper neural structure. The authors notice this problem and propose a new method to enlarge the space without much more search cost, which makes the approach more useful. 2. The proposed method is novel. There have already been some studies on NAS trying to introduce larger search space, but most are model specific. However, in this paper, the authors apply context-free grammars to model the search space, which is interesting and new. It’s easy for users to compose a considerable search space by allowing further derivations of the function composition. 3. The hierarchical search space is compatible with previous NAS methods. 4. The paper is well-written. The figures and descriptions are clear. It’s easy for readers, even researchers not in this area, to understand the main idea of this paper.

Weaknesses

1. In the proposed hierarchical search space, it’s more complicated to design a search space because the space must be described in context-free grammars, which is a little bit difficult. Does it take a lot of experience to design a search space based on context-free grammars for tasks? If one wants to apply this method in some other tasks, such as natural language processing or speech processing, can this method be easily used? Are there any suggestions for designing grammar? I suggest the authors clarify these issues in the next version. 2. A related problem, which I think is important, is that the authors restrict the discussion to fixed-length problems. It is not obvious how the method is applied to variable-length problems, such as those in NLP. I guess the problem would be much different if we deal with a sequence of variable length, but it is often the case in recent LLMs. 3. The use of CFG often leads to a compact representation of exponentially many structures. In this sense, the method discussed here is similar to methods that make use of compact data structures, such as DARTS. The advantage of using CFGs is that the method is itself well explained and training CFG-based systems has long been studied. On the other hand, this makes the work have overlap with previous work. 4. Pruning is generally used in CFG-based systems. But it is not covered in this work. This is not a concern but a possible improvement to current work.

Questions

Context-free grammars can well organize the search space and use clear rules to define a large search space, but what are the advantages of this approach for NAS? Although its search space has enlarged, a larger search space still requires more efficient search strategies to balance the search cost. What are the differences between your method and other previous work to expand the search space? For example, what is the main property of context-free grammars you think can help in NAS?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the limitations and discussed them in Section 7.

Summary

The authors propose improvements to several parts of the neural architecture search (NAS) pipeline. First, they introduce a methodology for specifying search spaces based on a combinator grammar that is both more flexible than previous structured search spaces and encourages more regularity and hierarchy than previous unstructured ones. They show that this methodology allows them to represent all search spaces they’re aware of from the literature, and extend them in ways that are likely to be helpful. Then they describe a method for searching these spaces using Bayesian optimization with a multiscale graph kernel and evolutionary operations, and show that this method achieves better results on existing search spaces (e.g., NAS-Bench-201 and DARTS) and even better results on hierarchical extensions of these search spaces (hierarchical NAS-Bench-201).

Strengths

The authors introduce good ideas and report strong results. They explicate and carefully follow NAS best practices, and use relatively little compute (only consumer GPUs!) while fostering reproducibility. Relative to a somewhat crowded field, the paper stands out as both careful and “obvious in retrospect”.

Weaknesses

The work is somewhat sprawling and can’t go into enough depth on some of the most interesting parts; e.g. the constraints section that explains that the CFG isn’t actually context-free is one paragraph long in the main paper, and all full network examples are in the appendix. Overall I have to put a lot of work in to understand where your advances fit in the big picture, and exactly what parts contribute to improved results. It also feels a bit like the last hurrah of a somewhat fading subfield (both convnet architecture optimization and convnet-focused NAS are perhaps a bit tapped out). A notational nit I have is that Residual(a, b, c) is a confusing way to write a structure where b is the residual for a and c. Is there any particular reason for this choice?

Questions

How far are we from “architectures from the book”? Was anything surprising about the architectural structures your method discovered? You mention some architecture search spaces that can’t be covered with a CFG (can you give an example?); are any important architecture classes locked out because of these search spaces?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

The authors adequately cover the limitations of their techniques. Two that particularly stood out to me are that the work assumes a computer vision/convnet context (e.g. special case handling of downsampling, no non-image-classification benchmarks) and lacks support for weight sharing.

Summary

This paper uses context-free grammar to improve the efficiency of neural architecture search. Experiments show that the proposed approach outperforms existing methods.

Strengths

- Simple, well-motivated and efficient approach to improve neural architecture search. - Clear presentation.

Weaknesses

No major weakness found, though the improvement presented in Table 2 seemed marginal. In addition, as the authors discussed in Section 7, the expressiveness of CFGs are limited to context-free languages, which may exclude the optimal architecture.

Questions

N/A

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have discussed the limitation of this paper: while adopting CFGs may limit the search space to context-free languages, empirical results have demonstrated effectiveness of the proposed approach.

Summary

The authors propose an approach to unify the search space for Neural Architecture Search (NAS) using context-free grammars. They further develop a Bayesian Optimization based search strategy to effectively explore a huge search space. They experiment over (proposed) hierarchical extension of NAS-Bench 201 benchmark to demonstrate sound improvements.

Strengths

Hierarchical search space design allows exploration of more controlled and viable architectures. While prior works mostly explored cell-based search, or require post-hoc checking, the authors develop a principled solution for macro to micro search using context-free grammars (CFG). In order to demonstrate their search granularity, the authors propose a hierarchical extension to NAS-Bench 201, and subsequently perform most of the experiments in the modified benchmark. The paper would benefit from also highlighting these results on the original NAS-Bench 201 benchmark to understand how the granularity of the search space impacts the different search methods in the traditional benchmark. In the modified hierarchical benchmark, the authors demonstrate strong performance improvements against several baseline methods. In Table 1, the authors contrast their search strategy against existing search strategies on multiple dimensions.

Weaknesses

1. While BOHNAS in general works well across multiple settings and outperforms several baselines, they do have limited gains when compared against DARTS and NASBOWL. 2. All the experiments and benchmarks in the paper focus on Conv based search spaces. Given that a lot of recent works, primarily on language models, focus on Transformer search spaces, a related discussion would be useful for the readers. 3. It will be nice to have results on larger datasets including the full ImageNet.

Questions

See above

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A