Neural architecture search (NAS) finds high performing networks for a given task. Yet the results of NAS are fairly prosaic; they did not e.g. create a shift from convolutional structures to transformers. This is not least because the search spaces in NAS often aren't diverse enough to include such transformations a priori. Instead, for NAS to provide greater potential for fundamental design shifts, we need a novel expressive search space design which is built from more fundamental operations. To this end, we introduce einspace, a search space based on a parameterised probabilistic context-free grammar. Our space is versatile, supporting architectures of various sizes and complexities, while also containing diverse network operations which allow it to model convolutions, attention components and more. It contains many existing competitive architectures, and provides flexibility for discovering new ones. Using this search space, we perform experiments to find novel architectures as well as improvements on existing ones on the diverse Unseen NAS datasets. We show that competitive architectures can be obtained by searching from scratch, and we consistently find large improvements when initialising the search with strong baselines. We believe that this work is an important advancement towards a transformative NAS paradigm where search space expressivity and strategic search initialisation play key roles.
Paper
Similar papers
Peer review
Summary
Neural Architecture Search (NAS) often produces incremental improvements due to limited diversity in traditional search spaces. To address this, the paper introduces "einspace," a versatile search space built from probabilistic context-free grammar (CFG). Einspace supports a wide range of architectures and operations, enabling the modelling of convolutions and attention mechanisms. Experiments on Unseen NAS datasets show that einspace can discover novel architectures from scratch and with grammars containing different foundation model architectures.
Strengths
1. The paper is written very clearly and examples of CFGs aid understanding of the paper. 2. The authors release code which improves the reproducibility of the work and potential future work 3. While I do think that this paper opens up new opportunities and challenges for scaling NAS from scratch to larger spaces and datasets, I have questions (check questions) for the authors to improve the quality of their evaluations and make a stronger case for the practical applicability of einspace.
Weaknesses
1. **Contribution**: Currently I fail to see the main contribution of the paper to the area to "searching architectures from scratch" [1]. I find the representation properties of the search space to be same as [1] (except the use of probabilistic CFGs). Moreover, the search schemes proposed random and evolutionary search are not very sample efficient in such large spaces compared to [1], which uses bayesian optimization with graph kernels. 2. **Evaluation**: The paper does not compare to natural baselines like [1]. Moreover I find the evaluation to be quite limited in terms of the datasets evaluated and the base models finetuned/evaluated on. [1] Schrodi, S., Stoll, D., Ru, B., Sukthanker, R.S., Brox, T. and Hutter, F., 2022. Towards discovering neural architectures from scratch.
Questions
Questions: 1, The paper claims that it is the first one to represent foundation model architectures with a NAS search space. However [1] already represented a language model using CFGs. Also [1] can potentially present any architecture (ViT, MLPMixer). Is my understandng correct that this paper introduces a PCFG on [1] to limit the search space size? I am also currently lacking a CFG which is a union of multiple foundation model architectures in a single grammar. Could the authors provide an example for this? 2. The paper uses random search and evo search, both of which are sample inefficient and do not scale well with the size of the dataset and search space. How do more sample efficient bayesian optimization algorithms perform here? 3. Currently the standard for small unseen datasets is finetuning a pretrained model on the smaller downstream task. Could the authors should ideally compare to for eg: simply finetuning a pretrained vision transformer or efficientnet on the unseen dataset? 4. Evaluation on larger datasets is missing. Architectures which are able to exploit dataset patterns change depending on the scale of datasets available (eg: Vision transformers [2]). Are the architectures discovered significantly different from the existing ones even when the dataset is scaled up. How efficient is the search on this scale? 5. Could you present parameter and FLOPs counts in Table 1? 6. How is the branching rate hyperparameter set for a newer search space? [1] Schrodi, S., Stoll, D., Ru, B., Sukthanker, R.S., Brox, T. and Hutter, F., 2022. Towards discovering neural architectures from scratch. [2] Raghu, M., Unterthiner, T., Kornblith, S., Zhang, C. and Dosovitskiy, A., 2021. Do vision transformers see like convolutional neural networks?. Advances in neural information processing systems, 34, pp.12116-12128.
Rating
4
Confidence
4
Soundness
3
Presentation
3
Contribution
2
Limitations
I do think that the paper opens up newer avenues of research in neural architecture search, however, given the limited evaluation I do have concerns about the applicability of the method. Check weakness and questions for details on the limitations. I am happy to raise my score if each of my concerns are appropriately addressed.
Response to rebuttal
I appreciate the efforts of the authors in addressing my questions I am increasing my score to 4. That said, I am still concerned about the parameter sizes of architectures discovered by einspace in most cases being much larger than architectures being compared with.
Response to reviewer
We thank the reviewer for their response and updated scores. We appreciate that there may be concern that at times our method finds architectures of higher parameter counts. However, we argue that this shows the flexibility of the search space in adapting to the difficulty of the given task. On three datasets (AddNIST, MultNIST and Chesseract) the parameter count is significantly increased, but in other cases it is significantly reduced (Language and Gutenberg). The increases could be easily controlled by either rejecting architecture candidates that are too big, or by including an efficiency component to the optimisation objective.
Summary
This paper proposes a new type of neural architecture search (NAS) search space that goes beyond standard, small NAS search spaces. Most popular search spaces in NAS are quite small, and include architectures that include known motifs because they are built around standard architectures. The authors point out that this is why NAS has failed to produce fundamentally new architectures, and instead, that most advancements in neural network architectures are from expert driven hand-design. Their search space, einspace, is a probabilistic context-free grammar (CFG) of fundamental operations.
Strengths
- The paper is well-written, well-motivated, and easy to follow. - The paper is clear in that its innovation is related to search space design, with many suggestions for possible search algorithms. The search space itself is quite impressive, and includes both convolutions as well as self-attention operations (built-up from more fundamental building blocks). - The results of search seem impressive -- while einspace does not always yield stronger architectures compared to other methods or hand-designed baselines, it does sometimes yield significantly better architectures. Furthermore, the comparison to the random search baseline is appreciated. - The search space supports initialization using existing architectures -- this is important for setting priors for problems in which good architectures are already known.
Weaknesses
- The resulting architectures in Table 1 do not always outperform SOTA architectures, but when they do, the improvement can be significant. On the other hand, there does not seem to be a comparison of the computational costs involved -- this would be helpful to include, especially as the search space is quite large. - The authors include results on NAS-Bench-360, which is great, however the results are incomplete and it is unclear why the authors only evaluate on 5 out of the 10 tasks. This seems particularly important as the motivation of einspace is similar to the line of work related to NAS-Bench-360. - In order to make search tractable, it seems like many assumptions are made on the priors on the search space. This makes sense, however, it would be interesting to explore variations on these choices more in-depth. If the authors adequately address these concerns, I will gladly raise my score.
Questions
- Out of curiosity, what do the authors view as the key reason for einspace not being able to express RNNs and SSMs? This is a valid design decision, but it also seems as though it should be fairly straightforward to design a version of einspace that supports recurrence (I could be mistaken about this). - Why did the authors choose the 5 NAS-Bench-360 tasks that were used in their evaluation? Does the method work on the other tasks?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
The authors clearly state the limitations, and even discuss avenues for future work. This includes extending the search space to handle recurrent architectures and state space models.
Summary
This paper proposes a new search space named einspace based on a parameterized probabilistic context-free grammar for neural architecture search. In contrast to conventional search space composed of high-level operations and modules such as recurrent layer, convolutional layer, and activation layer, einspace consists of more fundamental operations, such as clone, summation, permutation, and activation. This einspace can be defined by a context-free grammar and can represent the neural architecture as the derivation tree. The experiments on Unseen NAS and NAS-Bench-360 demonstrate the advantage of this search space.
Strengths
1. The paper is well-written and is easy to follow. 2. The idea of fundamental operations and context-free grammar for search space is great and interesting. 3. This search space has the advantage of designing new architectures based on existing SOTA architectures such as ResNet, Wide-ResNet, ViT, and MLP-Mixer.
Weaknesses
Despite the strengths of this paper, I still have some concerns that prevent me from confidently recommending acceptance: 1. The first problem is about the novelty. Since einspace is not the first search space based on CFG, and the fundamental operations of einspace are common in the existing search space, the novelty of einspace may not reach my expectations. Although the fundamental operations are different from and more expressive than the high-level operations and rigid structures of existing search space, these fundamental operations are also commonly used in existing search space. Furthermore, it is complicated to represent convolution and skip connection using these operations and it is impossible to represent recurrent computation, as the authors discussed in the Limitation section. 2. The second problem is about the tradeoff between diversity and time complexity of the search space. It would be better to analyze the time complexity or compare the time consumption between einspace and others, such as the space of DARTS. 3. From the experimental results, the architectures searched in einspace do not seem to be that competitive compared to other methods, as shown in Table 1. I think the results are also influenced by the search strategy. Is it possible to apply RL or differentiable search strategies to this search space? If possible, the author can give a table listing which search strategies are suitable for einspace and which search strategies are better.
Questions
See weaknesses.
Rating
6
Confidence
4
Soundness
4
Presentation
3
Contribution
3
Limitations
The authors have discussed the limitations in their paper. Besides, there are no potential negative societal impacts of this work.
Summary
The manuscript presents "einspace," a novel neural architecture search (NAS) space based on a parameterized probabilistic context-free grammar (CFG). The authors aim to address the limitations of current NAS methods by proposing a highly expressive search space that supports diverse network operations and architectures of varying sizes and complexities.
Strengths
1. The paper introduces a unique NAS search space, "einspace," which is designed to be highly expressive, accommodating a wide range of architectures, including those not traditionally found in NAS literature. 2. The work contributes to the ongoing discussion on the role of search space expressivity and strategic search initialization in NAS, potentially paving the way for future research in this direction.
Weaknesses
1. While the authors claim to introduce a new search space, the manuscript's Method Section appears to describe a set of rules that break down operators into smaller elements, which could be misinterpreted as a mere decomposition rather than a novel search space construct. This raises questions about the actual size and scope of the proposed search space, which would benefit from further clarification. 2. Section 3.7 is not clearly articulated, and the authors are encouraged to provide a simplified explanation of its main content to aid reader comprehension. 3. The primary goal of the proposed method is to design a highly expressive yet constrained search space. To substantiate this claim, it would be beneficial to conduct searches and validating on larger-scale datasets, such as ImageNet, which could more effectively demonstrate the superiority of the proposed search space. The current experiments on smaller datasets may not fully showcase the advantages of the search space. 4. The experimental settings are somewhat unclear. It appears that the authors search within the proposed space and then validate the discovered network structures on other datasets, such as those from NAS-Bench-360. However, NAS-Bench-360 imposes constraints on the design space that may not be compatible with the structures proposed by the authors. Further clarification on how the proposed space's network structures are adapted or validated on NAS-Bench-360 is needed to ensure the experiments are methodologically sound.
Questions
NA
Rating
4
Confidence
3
Soundness
2
Presentation
2
Contribution
2
Limitations
NA
Summary
This paper introduces einspace, a hierarchical space of neural architectures based on parametric probabilistic context free grammar, which is expressive enough to accommodate various state-of-the-art architectures including ResNets and Transformers. The Authors further perform Regularized Evolution (RE) search over einspace either searching from scratch or seeding the initial population with state-of-the-art architectures. In particular when seeded with ResNet18, RE generates novel architectures that significantly outperform ResNet18 on multiple datasets from Unseen NAS. Furthermore, RE both seeded with ResNet18 and Mix (a mixture of SOTA architectures) significantly outperform RE from scratch as well as random sampling and random search.
Strengths
This study extends previous research on hierarchical architecture spaces by introducing a more expressive framework capable of accommodating diverse structures including convolutional networks and transformers. Novelties include imposing minimal priors which facilitate successful search within a highly expressive architecture space. Additionally, grammar rules are equipped with parameters to ensure the generation of valid architectures through the combination of various components. Moreover, the complexity / depth of architectures are regulated by tuning the probabilities assigned to production rules. The authors demonstrate through a number of experiments involving ResNet and WideResNet architectures that network performance can be significantly enhanced by utilizing einspace in conjunction with RE, when seeding the initial population with these SOTA architectures.
Weaknesses
The experiments are currently limited. While the paper does not introduce a search strategy tailored to this search space, it is crucial to emphasize experiments demonstrating the potential for RE, possibly seeded with SOTA networks, to enhance model performance. The current evaluations focus on ResNet18 on the Unseen NAS datasets as well as WRN on datasets from NASBench360. Extending this analysis to include a broader range of models, e.g. those listed in Table.1 of Unseen NAS, such as AlexNet and DenseNet, would provide useful insights on the effectiveness of einspace. Moreover, it would be valuable to explore the application of RE on einspace to improve performance on widely used datasets like CIFAR10, e.g with ResNet and in particular ViT, given that the paper highlights the capability of einspace to support transformer architectures as an advantage.
Questions
How does einspace compare with other hierarchical search spaces in the literature [1] and [2] in terms of performance? To support the advantages of einspace, including expressivity at a reasonable search cost, it would be beneficial to conduct comparative evaluations, at least with RE, across a number of tasks. Does it make sense to apply black-box search methods other than RS, RE to einspace, for example the bayesian optimization-based methods BOHNAS and NASBOWL used in [2]? Approximate search times for RE on datasets of Table.1 are reported in appendix B.3. How do these search times compare with those of other NAS methods listed in Table.1? A similar comparison would also be valuable for the experiments in Table 5. [1] Hierarchical Representations For Efficient Architecture Search (Simonyan et.al 2018) [2] Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars (Schrodi et.al 2023)
Rating
5
Confidence
4
Soundness
3
Presentation
3
Contribution
2
Limitations
The limitations are adequately discussed in the final section.
Summary
This paper introduces einspace, a search space that is designed to hierarchically encode architectures using probabilistic context-free grammars (PCFG). It can encode various architectural components, such as convolutions, attention mechanisms, etc. The authors demonstrate the efficacy of simple blackbox optimizers in einspace to discover architectures that perform competitively on various tasks and datasets.
Strengths
In general the motivation to move beyond the conventional NAS spaces is valid and really important in my opinion. The paper is also very well-written, with simple examples followed by a more generic definition of the search space and interesting application to various tasks and datasets. Discovering novel architectures is a very challenging problem for the NAS community and as far as I know, this has not been achieved yet. Having a complex and versatile search space is the first step towards this goal. Some other positive aspects of this submission: - Interesting experiments showing the complexity of the search space and the need of guided search methods (e.g. evolutionary strategies as the authors show), instead of random search, which on previous spaces (e.g. the DARTS one) was shown to perform already well. - Available code that fosters reproducibility and enables easier future research on this topic. - Extending the prior work of [1] to probabilistic CFG. This enables (1) easier expert prior definitions on the search space, (2) a broader range of algorithms applied on einspace, that can as well incorporate uncertainty estimates of their choices inside the search itself.
Weaknesses
Despite the vast number of architectures that einspace includes, the major problem is how to search on these spaces in an efficient way. The prior work of [1] used BO with a hierarchical graph kernel (a novelty aspect of that paper), however that was still expensive, especially when moving to image classification tasks. I think defining search spaces that are very complex is very useful task, however, the NAS problem is not only solved by defining the search space alone. The search algorithm is a major component of the whole pipeline, and using blackbox methods to search in such search spaces will be computationally demanding and will still require company scale computation. Below I list my major concerns about this submission: - *Novelty*: I think the paper has some novel aspects compared to [1], e.g. the fact that can encode both attention-mechanisms and convolution, or other operators, or the probabilistic extension of the CFG. However, as the authors mention in the limitation section, it would be great if accompanying the search space, there would be a new proposed search method that can efficiently search on this space by exploiting the PCFG. - *Limitations of the search space*: As the authors mention, there are various important architectures that cannot be encoded in einspace. - *Claims*: I think the claim (for instance in the abstract) that you find "novel architectures" can mean many things. Correct me if I am wrong, but in my opinion einspace still encodes most of the known architectures, and searching on it will only re-discover them or improve on top of those architectures, but it won't find a completely novel architectural component, as for instance ResNets introduced the residual connection back then. - *Limited experimental evaluation and results*: The empirical evaluations are not enough in my opinion. The used tasks are simple and one function evaluation is cheap enough to allow blackbox methods to run there. Evaluating on more expensive tasks would require the development of more efficient search strategies that are tailored to einspace. Moreover the results shown in Table 1 are not that impressive considering RE is typically a very strong baseline, so I would have expected it to outperform all other methods.
Questions
- Could you please discuss further in more details on what are the main advantages of using CFG instead of graph-based or other encodings used in NAS [2]? -- References -- [1] https://proceedings.neurips.cc/paper_files/paper/2023/file/4869f3f967dfe954439408dd92c50ee1-Paper-Conference.pdf [2] https://proceedings.neurips.cc/paper/2020/file/ea4eb49329550caaa1d2044105223721-Paper.pdf
Rating
6
Confidence
5
Soundness
2
Presentation
4
Contribution
3
Limitations
The authors have addressed the limitations adequately.
Read the rebuttal and discuss with the authors
Hi Reviewers, The authors have submitted their rebuttal responses addressing the concerns and feedback you provided. We kindly request that you review their responses and assess whether the issues you raised have been satisfactorily addressed. If there are any areas where you believe additional clarification is needed, please do not hesitate to engage in further discussion with the authors. Your insights are invaluable to ensuring a thorough and constructive review process. Best AC
Thanks for the rebuttal.
After reading the rebuttal, I raise my score to 4 and lower my confidence. There is something I have misunderstood but I fail to figure it out.
Thanks for the response
We thank the reviewer for their response and for updating their scores. Let us know if there is anything we can clarify further to clear up the misconceptions, and we'll be happy to do so in the remaining discussion period.
Response to Authors
Thanks to the authors for the detailed rebuttal. Although there are some issues of einspace, such as high time complexity and complex representation of skip connections, I think it is a valuable exploration of the search space with atomic operations. Therefore, I would like to raise my score to Weak Accept.
Response to Reviewer wLBZ
We thank the reviewer for their response and updated scores. If there are any outstanding concerns regarding the time complexity or representations of architectural components, we are happy to discuss further during the discussion period.
I thank the Authors for their detailed response. Based on the additional results I would like to raise my score to 5.
Response to Reviewer s1qw
We thank the reviewer for their response and updated scores. If there are any outstanding concerns, we are happy to clarify further during the discussion period.
I thank the authors for their response and the additional experiments comparing einspace to the hierarchical NB201 space from Schrodi et al. I will increase my score, however, I think this paper has the potential to become a really strong publication by incorporating the feedback from the reviewers, and one more iteration might be beneficial in the long run.
Response to Reviewer duvy
We thank the reviewer for their response and their updated scores, and we are encouraged that they think our work has strong potential. We will integrate all feedback from this review process into our paper and for a potential camera-ready version we are also working towards evaluating a BO search strategy on our search space. Thank you for a great discussion.
Message to reviewer ZVSn
Thank you again for taking the time to review our paper. We hope our response has addressed your concerns, and would be very grateful if you would reconsider your scores. If there are further questions we are happy to continue discussing until the deadline tomorrow.
Decision
Accept (poster)