Towards Discovering Neural Architectures from Scratch
Authors: Simon Schrodi
Danny Stoll
Binxin Ru
Rhea Sanjay Sukthanker
Thomas Brox
Frank Hutter
Venue: Submitted to ICLR 2023 (2023)
Keywords: Neural Architecture Search
Search Space Design
Bayesian Optimization

Abstract: The discovery of neural architectures from scratch is the long-standing goal of Neural Architecture Search (NAS). Searching over a wide spectrum of neural architectures can facilitate the discovery of previously unconsidered but well-performing architectures. In this work, we take a large step towards discovering neural architectures from scratch by expressing architectures algebraically. This algebraic view leads to a more general method for designing search spaces, which allows us to compactly represent search spaces that are 100s of orders of magnitude larger than common spaces from the literature. Further, we propose a Bayesian Optimization strategy to efficiently search over such huge spaces, and demonstrate empirically that both our search space design and our search strategy can be superior to existing baselines. We open source our algebraic NAS approach and provide APIs for PyTorch and TensorFlow.

Under review as a conference paper at ICLR 2023
TOWARDS DISCOVERING NEURAL ARCHITECTURES FROM SCRATCH
Anonymous authors Paper under double-blind review
ABSTRACT
The discovery of neural architectures from scratch is the long-standing goal of Neural Architecture Search (NAS). Searching over a wide spectrum of neural architectures can facilitate the discovery of previously unconsidered but well- performing architectures. this work, we take a large step towards discover- ing neural architectures from scratch by expressing architectures algebraically. This algebraic view leads to a more general method for designing search spaces, which allows
compactly represent search spaces that 100s of orders of magnitude larger than common spaces from the literature. Further, we propose a Bayesian Optimization strategy efficiently search over such huge spaces, and demonstrate empirically that both our search space design and our search strategy can be superior existing baselines. We open source our algebraic NAS approach and provide APIs for PyTorch and TensorFlow.
INTRODUCTION
Neural Architecture Search (NAS), field with over 1 000 papers in the last two years (Deng & Lindauer 2022). is widely touted to automatically discover novel, well-performing architectural patterns. However, while state-of-the-art performance has already been demonstrated in hundreds of NAS papers (prominently, c.g., (Tan & Le 2019; 2021 Liu et al. (2019a)). success in automatically finding truly novel architectural patterns has been very scarce (Ramachandran et al. 2017 Liu al.
2020 For example, novel architectures, such as transformers (Vaswani et al. 2017 Dosovitskiy 2021 have been crafted manually and were found by NAS.
There is an accumulating amount evidence that over-engineered, restrictive search spaces (e.g.. cell-based ones) major impediments for NAS discover truly novel architectures. Yang et al. (2020b) showed that in the DARTS search space (Liu et al.] 2019b) the manually-defined macro architecture more important than the searched cells, while Xie al. (2019) and Ru al. (2020) achieved competitive performance with randomly wired neural architectures that do not adhere to common search space limitations. As a result, there are increasing efforts to break these impedi- ments, and the discovery of novel neural architectures has been referred to as the holy grail of NAS.
Hierarchical search spaces are a promising step towards this holy grail. In an initial work, Liu al. (2018) proposed a hierarchical cell, which is shared across fixed macro architecture, imitating the compositional neural architecture design pattern widely used by human experts. However, subse- quent works showed the importance of both layer diversity (Tan & Le 2019) and macro architecture (Xie et al. 2019 Ru et al. 2020).
In this work, we introduce general formalism for the representation of hierarchical search spaces, allowing both for layer diversity and flexible macro architecture. The key observation is that any neural architecture can be represented algebraically; e.g., two residual blocks followed by fully- connected layer in linear macro topology can be represented as the algebraic term
w = Lineer (iinear(Resiuuall((((a
id, conv), Residual(cony) id, conv), fc) (1)
We build upon this observation and employ Context-Free Grammars (CFGs) to construct large spaces of such algebraic architecture terms. Although particular search space is of course limited in its overall expressiveness, with this approach, we could effectively represent any neural architec- ture, facilitating the discovery of truly novel ones.

---

Under review as a conference paper at ICLR 2023
Due to the hierarchical structure of algebraic terms, the number of candidate neural architectures scales exponentially with the number of hierarchical levels, leading to search spaces 100s of orders of magnitudes larger than commonly used ones. To search in these huge spaces, we propose an efficient search strategy, Bayesian Optimization for Algebraic Neural Architecture Terms (BANAT), which leverages hierarchical information, capturing the topological patterns across the hierarchical levels, in its tailored kernel design.
Our contributions are as follows:
We present novel technique construct hierarchical NAS spaces based on algebraic notion views neural architectures as algebraic architecture terms and CFGs to create alge- braic search spaces (Section 2
We propose BANAT, a Bayesian Optimization (BO) strategy that uses a tailored modeling strategy to efficiently and effectively search over huge search spaces (Section 3
After surveying related work (Section 4). we empirically show that search spaces of alge- braic architecture terms perform on par or better than common cell-based spaces on dif- ferent datasets, show the superiority of BANAT over common baselines, demonstrate the importance of incorporating hierarchical information in the modeling, and show that we can find novel architectural parts from basic mathematical operations (Section 5)
We open source our code and provide APIs for Py PyTrrh (Paszke et al. 2019) and TensorFlow Abadi al. 2015) at https: /aopoy//nnnmmmous.... 4open. science/z/iclr23 tdnafs
2
ALGEBRAIC NEURAL ARCHITECTURE SEARCH SPACE CONSTRUCTION
In this section we present an algebraic view on Neural Architecture Search (NAS) (Section 2.1 and propose a construction mechanism based on Context-Free Grammars (CFGs) (Section 2.2 and
2.1 ALGEBRAIC ARCHITECTURE TERMS FOR NEURAL ARCHITECTURE SEARCH
We introduce algebraic architecture terms as string representation for neural architectures from (term) algebra. Formally, an algebra (A, F) consists of non-empty set A (universe) and set of operators f: A - F of different arities n 2 (Birkhoff) 1935). In our case, corresponds to the set of all (sub-)arcch jarhhtercctssssssss and we distinguish between two types of operators: (i) nullary operators representing primitive computations (c.g., conv() or fc()) and (ii) k-ary operators with Res Residuall dduall"";)))) :)). For sake of notational simplicity, we omit parenthesis for nullary operators (i.e., we write conv). Term algebras Baader & Nipkow 1999) are a special type of algebra mapping an algebraic expression its string representation. E.g.. we can represent a neural architecture as the algebraic architecture term w as shown in Equation [ Term algebras also allow for variables x; that are can be re-used across term. In our case, the intermediate variables can therefore share patterns across the architecture, c.g., shared cell. For example, we could define the intermediate variable an to map to the residual block in from Equation I follows:
k 0 representing topological operators (e.g., Linear(s
terms themselves that
w' = Linear(M1, 21, fc),
ReRReiduus cesidual(coony id, conv)
We formulate our algebraic view on NAS, where we search over algebraic archi- tecture terms w E Ω representing their associated architectures (w)). as follows:
Algebraic NAS
arg mig f(D(w)) wes
(3)
where f()) is an етrоr measure that we seek to minimize, e.g., final validation error of a fixed training protocol. For example, we can represent the popular cell-based NAS-Bench-201 search space(Dong & Yang 2020) algebraic search space L. The algebraic search space Ω is char- acterized by a fixed macro architecture Macro(...) that stacks 15 instances of a shared cell Cell(ps, Pi, P1. P1, Pi. P1), where the cell has six edges, on each of which one of five primi- tive computations can be placed (i.c., p: for E {1, 2, 3, 4, 5) corresponding to zero, id, convix1, x1, 3x,v3x3, or avg pool, respectively). By leveraging the intermediate variable
2

---

Under review as a conference paper at ICLR 2023
Algebraic architecture terms
Neural architectures
S
S
Linear(S, S, S)
Level 1
S
Linear(Residus duaa (S, ,, S, S), Residual(S, S, S), fc)
S
Ec
Level 2
id
Linear(Residual id, conv), Residual(conv, id, conv), fc)
cony conv Sony conv
Eo
Level 3
Figure 1: Derivations from Equation of algebraic architecture terms (left) correspond to edge replacements (Habel Kreowski 1983 1987 Drewes al. 1997) in the associated architecture (right), Appendix A provides the vocabulary for topological operators and primitive computations.
we can effectively share the cell topology across the architecture. For example, we can express an architecture wi Ω from the
search space f as:
Wj Macro (1, 21, I1 =
(4)
Algebraic NAS over such algebraic architecture terms then amounts to finding the best rest-performing primitive computation p, for each edge, as the macro architecture is fixed. In contrast to this simple cell-based algebraic space, the search spaces we consider can be much more expressive and, e.g., al- low for layer diversity and a flexible macro architecture over several hierarchical levels (Section 5.1
2.2 CONSTRUCTING NEURAL ARCHITECTURE TERMS WITH CONTEXT- GRAMMARS
We propose to use Context-Free Grammars (CFGs) (Chomsky 1956) since they can naturally gen- erate (hierarchical) algebraic architecture terms. Compared to other search space designs, CFGs give formally grounded way to naturally and compactly define very expressive hierarchical search spaces (e.g., see Section 5.J). We can also unify popular search spaces from the literature with our general search space design in one framework (Appendix [.]. They give us further simple mechanism to evolve architectures while staying within the defined search space (Section 3
Formally, CFG G (N, E, S) consists of finite set of nonterminals N and terminals E with N Kn = 0, a finite set of production rules P {A + 3/A E N, 3 E (N (N)"), where the asterisk denotes the Kleene operation (Kleene al. 1956), and start symbol S E N. To generate an algebraic architecture term, starting from the start symbol S, we recursively replace nonterminals of the current algebraic term with right-hand side of a production rule consisting of nonterminals and terminals, until the resulting string does not contain any nonterminals. For example, consider the following CFG in extended Backus-Naur form (Backus) 1959) (see Appendix B for background):
S Linear(S, S, S) Residual(S, S, S) conv id fc
(5)
From this CFG, we can derive the algebraic architecture term w (with three hierarchical levels) from Equation 1 as follows:
+ Linear(S, S, S)
Level
Lirrer(Ressicua S, S), Residual(S, (S, S, S), fc)
Level 2
+ Linear(Resiccual id, conv), Residual id, conv), fc) Level
Figure makes the above derivation and the connection to the associated architecture explicit. The set of all (potentially infinite) algebraic terms generated by CFG G is the language L(g), which naturally forms our search space Q. Thus, the algebraic NAS problem from Equation becomes:
arg min ((((w) wEL(S)
3

---

Under review as a conference paper at ICLR 2023
2.3 EXTENSIONS TO THE CONSTRUCTION MECHANISM
Constraints In many search space designs, we want to adhere to some constraints, e.g. to limit the number of nodes or to ensure that for all architectures in the search space there exists at least one path from the input to the output. We can simply do so by allowing only the application of production rules which guarantee compliance to such constraints. For example, to ensure that there is least one path from the input to the output, it is sufficient to ensure that each derivation connects its input to the output due to the recursive nature of CFGs. Note that this makes CFGs context-sensitive w.r.t those constraints. For more details, please refer to Appendix D
Fostering regularity through substitution To implement intermediate variables v; (Section 2.1 we leverage that context-free languages are closed under substitution: we map terminals, represent- ing the intermediate variables Fs, from one language algebraic terms of other languages, e.g., shared cell. For example, we can split a CFG G, constructing entire algebraic architecture terms, into the CFGs Gmoero and Goeu for the macro- or cell-level, respectively. Further, we add single (or multiple) intermediate terminal(s) 2 to Imacro which maps to an algebraic term W1 E L(Gcel)), e.g., the searchable cell. Thus, we effectively search over the macro-level as well as a single, shared cell. Note that by using fixed macro architecture (i.c.. (Gmmarro) = 1), we can represent cell-baser search spaces, e.g., MAS-Bench-201 (Dong Yang. 2020), while also being able to represent more expressive search spaces (e.g., see Section 5.1). More generally, we could extend this by adding further intermediate terminals which map to other languages L(G)), or by adding intermediate ter- minals to G2 which map to languages L(G)z1). In this way, we can effectively foster regularity.
Representing common architecture patterns for object recognition Neural architectures for object recognition commonly build a hierarchy of features that are gradually downsampled, e.g., by pooling operations. However, previous works in NAS were either limited to fixed macro architec- ture (Zoph et al.] 2018), only allowed for linear macro architectures (Liu et al. (019a)), or required
post-sampling testing for resolution mismatches (Stanley & Miikkulainen| 22022 Ru et al. 2020).
While this produced impressive performance on popular benchmarks (Tan & Le 2019 2021 Liu (tt al. 2019a), is an open research question whether different type of macro architecture (c.g., one with multiple branches) could yield even better performance.
To accommodate flexible macro architectures, we propose to overload the nonterminals. In par- ticular, the nonterminals indicate how often we apply downsampling operations in the subsequent derivations of the nonterminal. Consider the production rule D2 + Resi (D1,,, D2, D1), where Di with i E (1,2} are nonterminals which indicate that i downsampling operations have to be applied their subsequent derivations. That is, in both paths of the residual the input features will be downsampled twice and, consequently, the merging paths will have the same spatial resolution. Thereby, this mechanism distributes the downsampling operations recursively across the architec- ture. For the channels, we adopted the common design to double the number of channels whenever we halve the spatial resolution in our experiments, Note that we could also handle a varying number of channels by using, e.g., depthwise concatenation as merge operation.
3 BAYESIAN OPTIMIZATION FOR ALGEBRAIC NEURAL ARCHITECTURE SEARCH
We propose BO strategy, Bayesian Optimization for Algebraic Neural Architecture Terms (BA- NAT), to efficiently search in the huge search spaces spanned by our algebraic architecture terms: we introduce a novel surrogate model which combines Gaussian Process (GP) surrogate with a tailored kernel that leverages the hicrarchical structure of algebraic neural architecture terms (see below), and adopt expected improvement as the acquisition function (Mockus et al. 1978). Given the discrete nature of architectures, we adopt ideas from grammar-guider genetic programming (McKay et al. 2010 Moss et al.] 2020) for acquisition function optimization. Furthermore, to reduce wallclock time by leveraging parallel computing resources, we adapt the Kriging Believer (Ginsbourger et al., 2010) to select architectures at every search iteration so that we can train and evaluate them in parallel. Specifically, Kriging Believer assigns hallucinated values (i.e., posterior mean) of pending evaluations at each iteration to avoid redundant evaluations. For a more detailed explanation of BANAT, please refer Appendix F
4

---

Under review as a conference paper at ICLR 2023
Hierarchical Weisfeiler-Lehmar kernel (hWL) Inspired by the state-of faute-of-the art BO approach for NAS (Ru et al. 202T), we adopt the WL graph kernel (Shervashidze et al. 2011) in a GP surrogate, modeling performance of the algebraic architecture terms w, with the associated architectures (ww)). However, modeling solely based on the final architecture ignores the useful hierarchical information inherent in algebraic representation. Moreover, the large size of the architectures also makes it difficult to use single WL kernel to capture the more global topological patterns.
Since our hierarchical construction can be viewed as a series of gradually unfolding architectures, with the final architecture containing only primitive computations, we propose a novel hierarchical kernel design assigning a WL kernel to each hierarchy and combine them in a weighted sum. To this end, we introduce fold operators Fi, that removes algebraic terms beyond the 1-th hierarchical level. For example, the fold operators F1, F2 and F3 yield for the algebraic term w (Fquation D
Fs(w) = w = Liw.eaareeeiculaaccooooo
id, conv), Residual (esidual(conv,, id, conv), fc), (8)
[2) Linear(Residuall Residual, fc) Fi(w) Linear
Note the similarity to the derivations in Figure | Furthermore note that, in practice, we also add the corresponding nonterminals to integrate information from our hierarchical construction process. We define our hierarchical WL kernel (hWL) for two architectures ((wx) and (wry) with algebraic architecture terms wi or wy, respectively, constructed over hierarchy of levels, follows:
(1s, = (..kw(((FF(())) ((F((w))))
where the weights a govern the importance of the learned graph information at different hierarchical levels (granularities of the architecture) and can be tuned (along with other hyperparameters of the GP) by maximizing the marginal likelihood. We omit = 1 in the additive kernel Fi (w) does contain any edge features which are required for our WL kernel kw For more details on our novel hierarchical kernel design, please refer Appendix F2 Our proposed kernel efficiently captures the information in all algebraic term construction levels, which substantially improves its search and surrogate regression performance on our search space as demonstrated in Section 3
Acquisition function optimization To optimize the acquisition function, we adopt ideas from grammar-based genetic programming (McKay et al., 2010; Moss et al. 2020). For mutation, we randomly replace sub-architecture term with terminal as start symbol. For crossover, we randomly swap two sub-architecture terms with the same corresponding nonterminal. We consider two crossover operators: novel self-crossover operation swaps two sub-terms of single architecture term, and the common crossover operation swaps sub- terms of two different architecture terms. Importantly, all evolutionary operations by design only result in valid terms. We provide examples for the evolutionary operations in Appendix
randomly generated term, using the same non-
4 RELATED WORK
We discuss related works in NAS below and discuss works beyond NAS in Appendix G
Neural Architecture Search Neural Architecture Search (NAS) aims to automatically discover architectural patterns (or even entire architectures) (Elsken et al. 2019). Previous approaches, e.g., used reinforcement learning (Zoph & Le| 2017: Pham et 2018), evolution (Real et 2017).
gradient descent (Liu et al. 2019b). or Bayesian Optimization (BO) Kandasamy et al. [0188 8 White al., 2021; Ru et al.) (021). To enable the effective use of BO on graph-like inputs for NAS, previous works have proposed to use a GP with specialized kernels (Kandasamy et al., 2018 Ru jet al., (02T), encoding schemes (Ying et al., 2019 White et al. 2021). ). or graph neural networks as surrogate model (Ma et al.] Shi et al. 2020. 7020g et al. 2019). Different to prior works, we explicitly leverage the hicrarchical construction of architectures for modeling.
Searching for novel architectural patterns Previous works mostly focused on finding shared cell (Zoph et al. 2018) with a fixed macro architecture while only few works considered more ex- pressive hierarchical search spaces (Liu et al. 2018: 2019a Tan al. 2019). The latter works
5

---

Under review as a conference paper at ICLR 2023
considered hierarchical assembly (Liu al. 2018), combination of cell- and network-level search space (Liu et al.) 2019a Zhang et al. 2020), evolution of network topologies (Mikkulainen et al.) 2019). factorization of the search space (Tan et al. 2019), parameterization of hierarchy of ran- dom graph generators (Ru et al., 2020). a formal language over computational graphs (Negrinho) al. 2019), a hierarchical construction of TensorFlow programs (So al. 2021). Similarly, our formalism allows to design search spaces covering a general set of architecture design choices, but also permits the search for macro architectures with spatial resolution changes and multiple branches. We also handle spatial resolution changes without requiring post-hoc testing or resizing of the feature maps unlike prior works (Stanley & Miikkulainen [002] Miikkulainen et al. 2019
Stanley et al., 2019). Other works proposed approaches based on string rewriting systems (Kitano, 1990 Boers et al. 1993), cellular (or tree-structured) encoding schemes (Gruau) 1994 Luke &
Spector| 19%;; De Jong & Pollack 200T; Cai et al. 2018), hyperedge replacement graph grammars
Luerssen & Powers 3
2005). attribute grammars (Mouret & Doncieux, 2008), CFGs
(Jacob & Rehder [ouc/
Couchet et al. [207 Ahmadizar et al. 2015 Ahmad et al. al. 2019 Assunção
et al.
2017
2019:
Lima et al.) [019 de la Fuente Castillo et al. (020), or And-Or-gramman (Li
al.
2019
Different to these prior works, construct entire architectures with spatial resolu-
tion changes across multiple branches, and propose techniques to incorporate constraints and foster regularity. Orthogonal to the aforementioned approaches, Roberts et al. (2021) searched over neural (XD- JDD-Joperations, which is orthogonal to our approach, i.e., our predefined primitive computations could be replaced by their proposed XD-operations.
EXPERIMENTS
In this section, we investigate potential benefits of hierarchical search spaces and our search strategy BANAT. More specifically, we address the following questions:
Q1 Can hierarchical search spaces yield on par or superior architectures compared to cell-based search spaces with limited number of evaluations?
Q2 Can our search strategy BANAT improve performance over common baselines?
Q3 Does leveraging the hierarchical information improve performance?
Q4 Do zero-cost proxies work in vast hierarchical search spaces?
Q5 Can we discover novel architectural patterns (e.g., activation functions)?
To answer questions Q1-Q4, we introduce hierarchical search space based on the popular NAS-
Bench-201 search space (Dong & Yang 2020) in Section [5.] To answer question Q5, we search for activation functions (Ramachandran et al. 2017) and defer the search space definition to Ap-
pendix J.I We provide complementary results and analyses in Appendix 1.2 and J.3
5.1
HIERARCHICAL NAS-BENCH. 1
We propose a hierarchical variant of the popular cell-based & Yang 2020) by adding hierarchical maero space (i.e., spatial resolution flow and wiring the macro- macro-level) and parameterizable convolutional blocks (i.e., choice convolutions, activations, and normalizations). We express the hierarchical NAS-Bench-201 search space with CFG G, as follows:
search space (Dong
D2 = Li1ear3(D1, D1, DO) Linear3(Do, D1, D1) Linear D1, DO, DO)
D1 = Linear3(C, C, D)
Linear4(C, C, C, D) Residua13(C, C, D, D)
DO == Linear3(C, C, CL)
Linear4(C, C, C, CL) Residual3(C, C, CL, CL) Linear3(CL, CL, down) Resicual2(C, down, down)
D == Linear2(CI, down)
C Linear2(CI, CL)
Linear3(CI, CT.) Residua12(CI, CL. CT.)
CL == Cel1 OP, OP, OP, OP, OP)
OP == zero id BLOCK avg-pool
BLOCK = LACe, CONV, NORM)
ACT = relu hardswish mish
CONV convix1 conv3x3 dconv3x3
NORM == batch instance layer
(10)

---

Under review as a conference paper at ICLR 2023
See Appendix A for the terminal vocabulary of topological operators and primitive computations. The productions with the nonterminals (D2, D1, DO, D} define the spatial resolution flow and together with {C} define the macro architecture containing possibly multiple branches. The produc- tions for {CL, OP) construct the NAS-Bench-201 cell and (BLOCK, ACT, CONV, NORM) parameterize the convolutional block. To ensure that tive computations as in NAS-Bench-201.. we reweigh the sampling probabilities of the productions generated by the nonterminal OP, i... all production choices have sampling probability of 20 %, but BLOCK has 40 %. Note that we omit the stem (i.e., 3x3 convolution followed by batch nor- malization) and classifier (i.e., batch normalization followed by ReLU, global average pooling, and fully-connected layer) for simplicity. We implemented the merge operation as element- -wise summa- tion. Different to the cell-based NAS-Bench-201 search space, we exclude degenerated architectures by introducing a constraint that ensures that each subterm maps the input to the output (i.e., in the associated computational graph there is at least one path from source to sink).
the same distribution over the primi-
Our search space consists of ca. 10446 algebraic architecture terms (please refer to Appendix C on how to compute the search space size), which is significantly larger than other popular search spaces from the literature. For comparison, the cell-based WAS-Bench-22 search space is just minuscule subspace of size 104.18 where we apply only the blue-colored production rules and replace the CL nonterminals with placeholder terminal œ1 that will be substituted by the searched, shared cell.
5.2 EVALUATION DETAILS
For all search experiments, we compared the search strategies BANAT, Random Search (RS), Regu- larized Evolution (RE) (Real et al. 2019: Liu et al. 2018), and BANAT (WL) (Ru et al., (021). For implementation details of the search strategies, please refer to Appendix [H] We ran search for a total of 100 evaluations with a random initial design of 10 on three seeds {777, 888, 999} on the hierar- chical
search space or 1000 evaluations with a random initial design of 50 on one seed (777} on the activation function search space using 8 asynchronous workers each with single NVIDIA RTX 2080 Ti GPU. In each evaluation, we fully trained the architectures and recorded their last validation error. For training details on the hierarchical NAS-Bench-201 search space and activation function search space, please refer to Appendix [.1 or Appendix [12]] respectively.
To assess the modeling performance of our surrogate, compared regression performance of GPs with different kernels, i.e., our hierarchical WL kernel (hWL), (standard) WL. kernel (Ru et al. 2021), , and NASBOT's kernel (Kandasamy al., 2018). We also tried the GCN encoding (Shi al. 2020) but it could not capture the mapping from the complex graph space to performance. resulting in constant performance predictions. Further, note that the adjacency encoding ( (Ying et al. 2019) and path encoding (White et al. (02T) cannot be used in our hierarchical search spaces since the former requires the same amount of nodes across graphs and the latter scales exponentially in the number of nodes. We ran 20 trials over the seeds {0. 1, ..., 19} and re-used the data from the search runs. In every trial, we sampled a training and test set of 700 or 500 architecture and validation error pairs, respectively. We fitted the surrogates with a varying number of training samples by randomly choosing samples from the training set without replacement, and recorded Kendall's T rank correlation between the predicted and true validation error. To assess zero-cost proxies, re-used the data from the search runs and recorded Kendall's 7 rank correlation.
5.3 RESULTS
In the following we answer all of the questions Q1-QS. Figure compares the results of the cell- based and hierarchical search space design using our search strategy BANAT. Results with BANAT are on par on 1IFAR-10/100, superior on maaeNNet-16-122 AddNIST (answering Q1). We emphasize that the NAS community has engineered the cell-based search space to achieve strong performance on those popular image classification datasets for over a decade, making it unsurprising that our improvements are much larger for the novel datasets. Yet, our best found architecture on ImageNet-16- 120 from the hierarchical search space also achieves an excellent test error of 52.78 % with only 0.626 MB parameters (Appendix [.2]; this is superior to the architecture found by the of-te-oa-theaar method Shapley-NAS (i.e., 53.15 %) (Xiao et al.) 2022) and on par with the optimal architecture of the cell-based NAS-Bench (i.e., 52.69 % with 0.866 MB). Figure 3 shows that our search strategy BANAT is also superior
and clearly superior on CIFARTile and
search space
7

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CTFAR-100
Netteeett-16-120
CIFARTile
AddNIST
Val crror [%
32
58
50
9
40
28
100
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
hicrarchical
cell-basod
Figure/ 2: Cell-based vs. hierarchical search space. We plot mean and #1 standard error of the validation error on the hierarchical (solid blue) and cell-based (dashed orange) NAS-Bencha search space. We compare results using the other search strategies in Appendix T.2
CIFAR-10
CIFAR-100
ImageNet- 16-122
CIFARTile
AddNIST
Val error [%]
10
80
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
BANAT (ours)
RS
RE
BANAT (WL)
Figure 3: Comparison of search strategies the hierarchical search space. We plot mean and #1 standard eтrоr of the validation error on the hierarchical NAS-Bench-225 search space for our search strategy BANAT (solid blue), RS (dashed orange), RE (dotted green), and BANAT (WL) (dash- dotted red). We report test errors, best architectures, and conduct further analyses in Appendix I.2
to common baselines (answering Q2) and leveraging hicrarchical information clearly improves per- formance (answering Q3). Further, the evaluation of surrogate performance in [ that incorporating hierarchical information with our hierarchical WL. kernel (hWL) improves modeling, especially smaller amounts of training data (further answering Q3). Table shows that the base- line zero-cost proxies f flops and 12 -norm yield competitive (or often superior) results to more sophisticated zero-cost proxies; making hierarchical search spaces an interesting future research di- rection for them (answering Q4). Finally, Table 2 shows that we can find novel well perfforrfon activation functions from basic mathematical operations with BANAT (answering Q5).
DISCUSSION AND LIMITATIONS
While our grammar- baasd construction mechanism is pow- erful mechanism to construct huge hicrarchical search space, can not construct any architecture with grammar-based construction approach (Section 2.2 and 2.3) since we are lim- ited context-free languages; e.g., architectures of the type (a"t"c" E No cannot be generated by CFGs (this can be proven using Odgen's 's lemma (Ogden 1968)). Further, due to the discrete nature of CFGs we can not easily integrate contin- uous design choices, e.g., dropout probability. Furthermore, our grammar-basee mechanism does not (generally) support simple scalability of discovered neural architectures (e.g., rep- etition of building blocks) without special consideration in the search space design. Nevertheless, our search spaces still sig- nificantly increase the expressiveness, including the ability to represent common search spaces from the literature (see Appendix E for how we can represent the search spaces of DARTS, Auto-Deeplat the hierarchical cell search space of Liu et al. (2018), the Mobile-net search space, and the hierarchical random graph generator search space), as well as al- lowing search for entire neural architectures based around the popular HAS-Bench-201 search space
Search strategy
Test error [%]
ReLU
8.93
Swish
8.61
RS
8.91
RE
8.47
BANAT (WL)
8.32
BANAT (ours) 8.31
Table 2: Results of the activation function search on CIFAR-10 with ResNet-20.
8

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CIFAR-100
CIFARTile
AddNIST
Kendall's
0.7
0.7
0.6
0.7
0.7
0.6
0.6
0.5
0.5
0.5
0.5
0.4
0.4
400
400
400
#train samples
#train samples #train samples #train samples
#train samples
hWL
w/o hWL
NASBOT
Figure 4: Mean Kendall's т rank correlation with #1 standard error achieved by GP with our hierarchical WL kernel (hWL), (standard) WL kernel (WL), and NASBOT (Kandasamy et al. 2018).
Table I: Kendall's r rank correlation of zero-cost-proxies on our hierarchical NAS- MAS-Bench-201 space. Note that zen and nwot may not be suitable for hierarchical search space, they are specifically designed for architectures with batch normalization and ReL.U non-linearity, respec- tively. We still report exemplary search results for NASWOT (Mellor al. 202T) in Appendix 1.2
since it is the best non-baseline zero-cost proxy across the datasets.
Zero-cost proxy
CIFAR-I0
CIFAR-100
ImageNet16-120
CIFARTile
AddNIST
plain Abdelfattah et al.
2021
-0.01
0.01
-0.08
-0.0
0.04
params (Ning et al. 2021
0.39
0.13
0,28
0.5
flops (Ning et al. 2021
0.46
0.51
0.47
0.47
0.49
norm (Abdeliattah al.
2021
0,34
0.51
zen: score [L.nn al.
2021
0.47
0,24
0.4
fisher (Tumeer ct al. 2020
-0.06
-0.03
-0.05
0,03
grad-norm (Abdciatta et
2021
0.09
0.15
0.24
grasp Wang et 20200
0.08
0.17
0,02
0.03
snip [Lee al. 2019
0.17
-0.01
0.21
0.29
syn.flow Lanaiaa al
0.06
-0.18
-0,08
epe-nas Lopes al 2021
0.34
0,23
jacev MMelorr
0.34
0.34
0.25
0.12
rwot
Mellor et al.,
0.32
0.44
0.58
0.34
0.22
Thus, search space design facilitate the discovery of novel well sell-performing ral architectures in those huge search spaces algebraic architecture terms.
(Section 5.
However, there is inherent trade-off between the expressiveness and the difficulty of search. The much greater expressiveness facilitates search in a richer set of architectures that may include better architectures than in more restrictive search spaces, which however need not exist. Besides that, the (potential) existence of such a well-performing architecture does not result in a search strategy discovering even with large amounts of computing power available. Note that the trade- off manifests itself also in the acquisition function optimization of our search strategy BANAT.
In addition, well-performing neural architecture may work with current training protocols and hyperparameters due to interaction effects, i.c., training protocols and hyperparameters may be over- optimized for specific types of neural architectures. To overcome this limitation, one could consider joint optimization of neural architectures, training protocols, and hyperparameters. However, this further fuels the trade-off between expressiveness and the difficulty of search.
7 CONCLUSION
We introduced very expressive search spaces of algebraic architecture terms constructed with CFGs. To efficiently search over the huge search spaces, we proposed BANAT, efficient BO strategy with a tailored kernel leveraging the available hierarchical information. Our experiments indicate that both our search space design and our search strategy can yield strong performance over existing baselines. Our results motivate further steps towards the discovery neural architectures based on more atomic primitive computations. Furthermore. future works could (simultaneously) learn the search space (i.c., learn the grammar) or improve search efficiency by means of multi-fidee multi-fidelity optimization or gradient-based search strategies.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we address all points of the best practices checklist for NAS research (Lindauer& & Hutter 2020 in Appendix K
ETHICS STATEMENT
NAS has immense potential to facilitate systematic, automated discovery of high-performing (novel) architecture designs. However, the restrictive cell-based search spaces most commonly used in NAS render it impossible to discover truly novel neural architectures. With general formalism based on algebraic terms, we hope to provide fertile foundation towards discovering nigh-performing and efficient architectures; potentially from scratch. However, search in such huge search spaces is expensive, particularly in the context of the ongoing detrimental climate crisis. While on the one hand, the discovered neural architectures, like other AI technologies, could potentially be exploited to have negative societal impact; on the other hand, our work could also lead to advances across scientific disciplines like healthcare and chemistry.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, An- drew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Man- junath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng, TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems, 2015.
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas D Lane. Zero-Cost Proxies for Lightweight NAS. In International Conference on Learning Representattons, 2021.
Qadeer Ahmad, Atif Rafiq, Muhammad Adil Raja, and Noman Javed. Evolving MIMO multi- layered artificial neural networks using grammatical evolution. In Proceedings of the ACM Sym- posium on Applied Computing, 2019.
Fardin Ahmadizar, Khabat Soltanian, Fardin AkhlaghianTab, and Ioannis Tsoulos. Artificial neural network development by means of novel combination of grammatical evolution and genetic algorithm. Engineering Applications of Artificial Intelligence, 2015.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances in Neural Information Processing Systems, 2016.
Filipe Assunção, Nuno Lourenço, Penousal Machado, and Bernardete Ribeiro. Automatic genera- tion of neural networks with structured grammatical evolution. In IEEE Congress on Evolutionary Computation, 2017.
Filipe Assunção, Nuno Lourenço, Penousal Machado, and Bernardete Ribeiro. DENSER: deep evolutionary network structured representation. Genetic Programming and Evolvable Machines, 2019.
Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge university press, 1999.
John Warner Backus. The syntax and semantics of the proposed international algebraic language of the zurich com-gamm conference. In International Conference on Information Processing, 1959.
Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoe V. Le. Neural Optimizer Search with Rein- forcement Leaming. In International Conference Machine Learning, 2017.
Garrett Birkhoff. On the structure of abstract algebras. Mathematical Proceedings of the Cambridge Philosophical Society, 1935.
10

---

Under review as a conference paper at ICLR 2023
Egbert J. W. Boers, Herman Kuiper. Bart L. M. Happel, and Ida G. Sprinkhuizen Kuyperr Biological Metaphors In Designing Modular Artificial Neural Networks. In International Conference on Artificial Neural Networks, 1993.
Eric Brochu, Vlad M. Cora, and Nando De Freitas. A Tutorial on Bayesian Optimization of Expen- sive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning. arXiv, 2010.
Han Cai, Jiacheng Yang. Weinan Zhang, Song Han, and Yong Yu. Path-Level Network Transforma- tion for Efficient Architecture Search. In International Conference on Machine Learning, 2018.
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to Optimize: A Primer and Benchmark. Journal of Machine Learning Research, 2022a.
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Yao Liu, Kaiyuan Wang, Cho-Jui Hsich, Yifeng Lu, and Quoe V. Le. Evolved Optimizer for Vision. In First Conference on Automated Machine Learning Klate-Breaking Workshop), 2022b.
Yutian Chen, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P. Lillicrap. Matt Botvinick, and Nando Freitas. Learning to Learn without Gradient Descent by Gradient Descent. In International Conference on Machine Learning, 2017.
Noam Chomsky. Three models for the description of language. IRE Transactions on information theory, 1956.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A Downsampled Variant of ImageNet as an Alternative to the CIFAR Datasets. arXiv, 2017.
Jorge Couchet, Daniel Manrique, and Luis Porras. Grammar-Guuided Neural Architecture Evolution. In International Work-Conference on the Interplay Between Natural and Artificial Computation, 2007.
Guofeng Cui and He Zhu. Differentiable Synthesis of Program Architectures. In Advances in Neural Information Processing Systems, 2021.
Edwin D. De Jong and Jordan B. Pollack. Utilizing Bias to Evolve Recurrent Neural Networks. In International Joint Conference on Neural Networks, 2001.
Víctor de la Fuente Castillo, Alberto Diaz-Álvarez Miguel-Angel Manso-Calleja and Francisco Serradilla Garcia. Grammar Guided Genetic Programming for Network Architecture Search and Road Detection on Aerial Orthophotography, Applied Sciences, 2020.
Difan Deng and Marius Lindauer. Literature on Neural Architecture Search. https://www/t www. -a-
automl. [Online; accessed 25- S-etteemerr-2022].
2022.
Xuanyi Dong and Yi Yang. MAS-Bench-200 Extending the Scope of Reproducible Neural Archi- tecture Search. In International Conference Learning Representations, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In International Conference on Learning Representations, 2021.
Frank Drewes, Höns-Jörg Kreowski, and Annegret Habel. Hyperedge replacement graph gram- mars. Handbook Of Graph Grammars And Computing By Graph Transformation: Volume I: Foundations. World Scientific, 1997.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural Architecture Search: A Survey. Journal of Machine Learning Research, 2019.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ, Math. Inst. Hung. Acad. Sci, 1960.
11

---

Under review as a conference paper at ICLR 2023
Alexander L Gaunt, Mare Brockschmidt, Nate Kushman, and Daniel Tarlow. Differentiable pro- grams with neural libraries. In International Conference on Machine Learning, 2017.
Rob Geada, Stephen McGough, Amir A. Abarghouei, Isabelle Guyon, and Sébastien Treguer. CVPR-NAS-Datassess (codebase for the "CVPR-NAS 2021 Unseen Data Track"). https: //gi http://ccc/oooeeeaa//ryyoyo
nas saaasddatasess 2021.
David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro. Kriging is well-suited to parallelize optimization. In Computational Intelligence in Expensive Optimization Problems. Springer, 2010.
Frederic Gruau, Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm. PhD thesis, Laboratoire de I'Informatique du Parallilisme, Ecole Normale Supirieure de Lyon, 1994.
Annegret Habel and Hans-Jörg Kreowski. On context-free graph languages generated by edge re- placement. In Graph-Grammars and Their Application to Computer Science, 1983.
Annegret Habel and Hans-Jörg Kreowski. Characteristics graph languages generated by edge
replacement. Theoretical Computer Science, 1987.
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2016.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-Exiinee Conference on Computer Vision and Pattern Recognition, 2018.
Networks. In Proceedings of the IEEE/CVF
Christian Jacob and Jan Rehder. Evolution of neural net architectures by a hierarchical grammar- based genetic system. In Artificial Neural Nets and Genetic Algorithmss 1993.
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabás Póczos, and Eric P. Xing. Neural Architecture Search with Bayesian Optimisation and Optimal Transport. In Advances in Neural Information Processing Systems, 2018.
Hiroaki Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex systems, 1990.
Stephen C. Kleene et al. Representation of events in nerve nets and finite automata. Automata studies, 1956.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images, 2009.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr SNIP: Single-shot Network Pruning based Connection Sensitivity. International Conference Learning Representations, 2019.
Ke and Jitendra Malik. Learning to Optimize. International Conference on Learning Represen- tations, 2017.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertuinty in artificial intelligence, 2020.
Xilai Li, Xi Song, and Tianfu Wu. AOGNets: Compositional grammatical architectures for deep
learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogni- tion, 2019.
Ricardo H. R. Lima, Aurora T. R. Pozo, and Roberto Santana. Automatic Design of Convolutional Neural Networks using Grammatical Evolution. In Brazilian Conference on Intelligent Systems, 2019.
Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-NAS: A Zero-Shot NAS for High-Performance Image Recognition. Proceedings of the IEFF/CVF International Conference Computer Vision, 2021.
12

---

Under review as a conference paper at ICLR 2023
Marius Lindauer and Frank Hutter. Best practices for scientific research on neural architecture search. Journal of Machine Learning Research, 2020.
Chenxi Liu, Liang-Chich Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L. Yuille, and Li Fei-Fei. Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmen- tation. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019a.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hier- archical Representations for Efficient Architecture Search. In International Conference on Learn- ing Representations, 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable Architecture Search. In International Conference on Learning Representations, 2019b.
Hanxiao Liu, Andy Brock, Karen Simonyan, and Quoc V. Le. Evolving AoimalizationAAciiaatii Layers. Advances in Neural Information Processing Systems, 2020.
Vasco Lopes, Saeid Alirezazadeh, and Luís A Alexandre. EPE-NAS: Efficient Performance Estima- tion Without Training for Neural Architecture Search. In International Conference on Artificial Neural Networks, 2021.
Hyy Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. In International Con- ference on Learning Representations, 2019.
Martin H. Luerssen. Graph Grammar Encoding and Evolution of Automata Networks. In Aus- tralasian Conference on Computer Science, 2005.
Martin H. Luerssen and David M. W. Powers. On the Artificial Evolution of Neural Graph Gram- mars. University of New South Wales, 2003.
Sean Luke and Lee Spector. Evolving Graphs and Networks with Edge Encoding: Preliminary Report. In Late-breaking Papers of the Genetic Programming 96 conference, 1996.
Lizheng Ma, Jiaxu Cui, and Bo Yang. Deep Neural Architecture Search with Deep Graph Bayesian Optimization. In IEEE/WIC/ACM International Conference on Web Intelligence. IEEE Computer Society Press, 2019.
Robert I. McKay, Nguyen Xuan Hoai, Peter A. Whigham, Yin Shan, and Michael O'neill. Grammar- based genetic programming: a survey. Genetic Programming and Evolvable Machines, 2010.
Joe Mellor, Jack Turner, Amos Storkey, and Elliot Crowley. Neural Architecture Search without Training. In International Conference on Machine Learning, 2021.
Risto Mikkulainen, Jason Liang, Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, et al. Evolving Deep Neural Networks. In Artificial Intelligence in the Age of Neural Networks and Brain Computing. Elsevier, 2019.
Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The Application of Bayesian Methods for Seeking the Extremum. Towards Global Optimization, 1978.
Henry Moss, David Leslie, Daniel Beck, Javier González, and Paul Rayson. BOSS:
Bayesian Opti-
mization over String Spaces. In Advances in Neural Information Processing Systems, 2020.
Jcan-Baptiste Mouret and Stéphane Doncieux. MENNAG: a modular, regular and hierarchical en- coding for netral-networks based on attribute grammars. Evolutionary Intelligence, 2008
Renato Negrinho, Matthew Gormley, Geoffrey J. Gordon, Darshan Patil, Nghia Le, and Daniel Fer- reira. Towards modular and programmable architecture search. Advances in Neural Information Processing Systems, 2019.
Xuefei Ning, Changcheng Tang, Wenshuo Li, Zixuan Zhou, Shuang Liang, Huazhong Yang, and Yu Wang. Evaluating Efficient Performance Estimators of Neural Architectures. Advances in Newral Information Processing Systems, 2021.
13

---

Under review as a conference paper at ICLR 2023
William Ogden. A helpful result for proving inherent ambiguity. Mathematical systems theory, 1968.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Peefformncce Deep Learning Library. In Advances in Neural Information Processing Systems, 2019.
Hieu Pham, Melody Guan, Barret Zoph, Quoe V. Le, and Jeff Dean. Efficient Neural Architecture Search via Parameters Sharing. International Conference on Muchine Learning, 2018
Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for Activation Functions. arXiv, 2017.
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoe V. Le, and Alexey Kurakin. Large-Scale Evolution of Image Classifiers. In International Conference on Machine Learning, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized Evolution for Image Classifier Architecture Search. In Proceedings of the National Conference Artificial Intelli- gence, 2019.
Esteban Real, Chen Liang, David So, and Quoc V. Le. AutoML-Zerro Evolving Machine Learning Algorithms From Scratch. In International Conference on Machine Learning, 2020.
Nicholas Roberts, Mikhail Khodak, Tri Dao, Liam Li, Christopher Ré, and Ameet Talwalkar. Re- thinking Neural Operations for Diverse Tasks. Advances in Neural Information Processing Sys- fems, 2021.
Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kerness. In International Conference on Learning Representations, 2021.
Robin Ru, Pedro Esperança, and Fabio Maria Carlucci. Neural architecture generator optimization. In Advances in Neural Information Processing Systems, 2020.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Cli Shang-Chich Chen. Mo- bileNetV2: Inverted Residuals and Linear Bottlenecks. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, 2018
Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. Learn- ing Differentiable Programs with Admissible Neural Heuristics. Advances in Neural Information Processing Systems, 2020.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando De Freitas. Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proceedings of the IEEE, 2015.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research, 2011.
Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the Gap between Sample-based and One-shot Neural Architecture Search with BONAS. In Advances in Neural Information Processing Systems, 2020.
David So, Wojeiech Manke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoc V. Le. Searching for Efficient Transformers for Language Modeling. Advances in Neural Information Processing Systems, 2021.
Kenneth O. Stanley and Risto Mikkullanen. Evolving Neural Networks through Augmenting Topologies. Evolutionary Computation, 2002.
Kenneth O Stanley, Jeff Clune, Joel Lehman, and Risto Mikkulainen.. Designing neural networks through neuroevolution. Nature Machine Intelligence, 2019.
14

---

Under review as a conference paper at ICLR 2023
Mingxing Tan and Quoc V. Le. EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. In International Conference on Machine Learning, 2019.
Mingxing Tan and Quoe V. Le. EfficientNetV2:: Smaller Models and Faster Training, In Interna- tional Conference on Machine Learning, 2021.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V. Le. MnasNet: Platform-Aware Neural Architecture Search for Mobile. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Pro- cessing Systems, 2020.
Jack Turner, Elliot J Crowley, Michael O'Boyle, Amos Storkey, and Gavin Gray, BlockSwap: Fisher-guided Block Substitution for Network Compression on a Budget. International Confer- ence on Learning Representations, 2020.
Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong Learning as Program Synthesis. Advances in Neural Information Processing Systems, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. Advances in Neural Information Processing Systems, 2017.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking Winning Tickets Before Training by Preserving Gradient Flow. International Conference Learning Representations, 2020.
Ruochen Wang, Yuanhao Xiong, Minhao Cheng, and Cho-Jui Hsieh. Efficient Parameeti Optimizer Search for Diverse Tasks, Advances in Neural Information Processing Systems, 2022.
Duncan Watts and Steven H. Strogatz. Collective dynamics of 'srldl-wordd' networks. Nature, 1998.
Colin White, Willie Neiswanger, and Yash Savani. BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search. In Proceedings of the National Conference on Artificial Intelligence, 2021.
Han Xiao, Ziwei Wang. Zheng Zhu, Jie Zhou, and Jiwen Lu. Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2022.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring Randomly Wired Neu- ral Networks for Image Recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. Nas evaluation is frustratingly hard. International Conference on Learning Representations, 2020a.
Antoine Yang. Pedro M. Esperança, and Fabio M. Carlucci. NAS evaluation is frustratingly hard. In International Conference on Learning Representations, 2020b.
Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter. NAS- Bench- 101: Towards Reproducible Neural Architecture Search. In International Conference on Machine Learning. 2019.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph HyperNetworks for Neural Architecture Search. In International Conference on Learning Representations, 2019.
Haokui Zhang, Ying Li. Hao Chen, and Chunhua Shen. Memory-Efficiee Hierarchical Neural Ar- chitecture Search for Image Denoising. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
15

---

Under review as a conference paper at ICLR 2023
Barret Zoph and Quoe V. Le. Neural Architecture Search with Reinforcement Learning. In Interna- tional Conference on Learning Representations, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V. Le. Learning Transferable Architec-
tures for Scalable Image Recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2018.
16

---

Under review as a conference paper at ICLR 2023
A FROM TERMINALS TO PRIMITIVE COMPUTATIONS AND TOPOLOGICAL OPERATORS
Table and and 3 desscribe the primitive computations and topological operators used throughout experiments in Section 5 and Appendix respectively. Note that by adding more primitive computations and/or topological operators we could construct even more expressive search spaces.
Table 3: Primitive computations. "Name" corresponds to the string terminals in our CFGs and "Function" is the associated implementation of the primitive computation in pseudocode. The sub- scripts 9. k, and p abbreviations for groups, kernel size, strides, and padding, respectively. During assembly of neural architectures (w)), we replace string terminals with the associated prim- itive computation.
Name
Function
avg-pool
Avp (x)
batch
BN (x)
convixl
ConVi=1,==1,=001
conv3x3
Conv==3,==1==100)
dconv3x3
ConVg=Ck=st==1==00))
down
| (x))
Con (AvgPoola-2.ess) (x))
hardswish
Hardswish (x)
id
Identitiy (x)
instance
IN (x)
layer
IN (x)
mish
Mish (x)
relu
ReLU (x)
zero
Zeros (x)
b 1000000
(a) Linear2(a, b).
(b) Linear3(a, c).
(c) Linear4(a, b, d).
d
e
Resi duall(a, 2(a, (c) Residual 3(a, c. b,
Figure 5: Topological operators. Each subfigure makes the connection between the topogolocial operator and associated computational graph explicit, i.e., the arguments of the graph operators (a. b....) are mapped to the respective edges in the computational graph.
B EXTENDED BACKUS-NAUR FORM
The (extended) Backus-Nar form Backus 1959 is a meta-language to describe the syntax of CFGs. We use meta-rules of the form S (N U)* a string of nonterminals and/or terminals. We denote nonterminals in UPPER CASE, terminals corresponding topological operators in Initial upper case/teletype and terminals corresponding to primitive computations in lower case/teletype, e.g., S := Res desidual(S. S, id). To compactly express production rules with the same left-hand side nonter- minal, we use the vertical bar to indicate choice production rules with the same left-hand side, e.g., S = I. Linear(S. S, S) Residual (S, S, id) conv.
where S N is nonterminal and a
17

---

To implement the constraint "only consider valid neural architectures", we note that our search space design only creates neural architectures where neither the spatial resolution nor the channels can be mismatched; please refer to Section 2 for details. Thus, the only way a neural architecture can become invalid is through zero operations, which could remove edges from the computational graph and possibly disassociate the input from the output. Since we recursively assemble neural architectures, it is sufficient ensure that the derived algebraic architecture term (i.e., the associated computational graph) is compliant with the constraint, i.e.,there is at least one path from input to Under review as a conference paper at ICLR 2023
C SEARCH SPACE SIZE
In this section, we show how to efficiently compute the size of our search spaces constructed by CFGs. There are two cases to consider: (i) a CFG contains cycles (i.e., part of the derivation can be repeated infinitely many times), yielding open-ended, infinite search space; and (ii) CFG contains no cycles, yielding in a finite search space whose size we can compute.
Consider production A Residuai(B, B, B) where Residual is terminal, and A and are nonterminals with - conv id. Consequently, there are 2 = 8 possible in- stances of the residual block. If we add another production choice for the nonterminal A, e.g-, + Linear(B, B, B), we would have + 23 = 16 possible instances. Further, adding a production + (inear(A, A, A) would yield search space size of (2 2 4096.
More generally, we introduce the function PA that returns the set of productions for nonterminal A E N, and the function μ : P N that returns all the nonterminals for production p P. We can then recursively compute the size of the search space as follows:
p(p) 0
f(A) = Σ
II S(A') A'Eu(p)
otherwise
(11)
PEPA
When CFG contains some constraint, ensure to only account for valid architectures (i.e., com- pliant with the constraints) by ignoring productions which would lead to invalid architectures.
D MORE DETAILS ON SEARCH SPACE CONSTRAINTS
During the design of the search space, may want comply with some constraints, e.g., only con- sider valid neural architectures impose structural constraints architectures. We can guarantee compliance with constraints by modifying sampling (and evolution): we only allow the application of production rules, which guarantee compliance with the constraint(s). In the following, we show exemplary how this can be implemented for the former constraint mentioned above. Note that other constraints can be implemented in a similar manner
output. Thus, during sampling (and similarly during evolution), modify the current production rule choices when an application of the zero operation would disassociate the input from the output.
E COMMON SEARCH SPACES FROM THE LITERATURE
In Section 5.T we demonstrated how to construct the popular MAS-Bench-201 search space within algebraic search space design, and below show how to reconstruct the following popular search spaces: DARTS search space (Liu et al.] 2019b). Beco-Dee search space (Liu et al. 2019a), hierarchical cell search space (Liu et al. 2018), Mobile-net search space (Tan al.] 2019). and hterarchical random graph generator search space (Ru et al. 2020). For implementation details refer to the respective works.
DARTS SEARCI SPACE
The DARTS search space (Liu et al. 2019b) consists of a fixed macro architecture and a cell, i.e., a seven node directed acyclic graph (Darts: see T the topological operator). We omit the fixed macro architecture from our search space design for simplicity. Each cell receives the feature maps from the two preceding cells input and outputs single feature map. All intermediate nodes
18

---

Under review as a conference paper at ICLR 2023
{
Node3
Node4
Node5
Node6
k
Figure 6: Visualization of the Darts topological operator.
(i.e., Node3, Node4, Node5, and Node is computed based on all of its predecessors. Thus, we can define the DARTS search space follows:
DARTS Darta(NODE3, NODE4, NODES, NODE6)
NODE3 Node3(OP, OP)
NODEA = (OP, OP, OP)
NODE5 := Nod:5(OP, OP, OP, OP)
(12)
NODE6 :: Node5(OP, OP, OP, OP, OP)
OP ::= sep.conv.3x3 sep.conv_5x5 dil_conv_3x3 dil.conv.5xx
max.pool avg-pool id zero
where the topological operator Node receives two inputs, applies the operations separately them, and sums them up. Similarly, Node 4, Node5, and Node apply their operations separately to the given inputs and sum them up. The topological operator Darts feeds the corresponding feature maps into each of those topological operators and finally concatenates all intermediate feature maps.
AUTO-DEEPLAB SEARCH SPACE
Auto-Deepl .ab (Liu et al. 2019a) combines cell-level with network-level search space search for segmentation networks, where the cell is shared across the searched macro architecture, i.c., twelve step (linear) path across different spatial resolutions. The cell-level design is adopted from Liu et al. (20195) and, thus, we can re-use the CFG from Equation 12 For the network-level, introduce constraint that ensures that the path is of length twelve, i.e., we ensure exactly twelve derivations in our CFG. Further, we overload the nonterminals so that they correspond to respective spatial resolution level, e.g., D4 indicates that the original input downsampled by a factor of four; please refer to Section 2.3 for details on overloading nonterminals. For the sake of simplicity, we omit the first two layers and atrous spatial pyramid poolings as they are fixed, and hence define the network-level search space as follows:
D4 :: Same(CELL, D4) Down(CELL, D8)
D8 Up(CELL, D4) Same(C D8) Dowa(CELL, D16)
(13)
D16 Up(CELI, D8) Same(CELL, D16) Down(CELL,, D32)
D32 : Up(CELI, D16) Same(CELL, D32)
where the topological operators Up, Same, and Down upsampic/halve, do not change/do not change, or downsample/double the spatial resolution/chamnels respectively. The placeholder variable CELL maps the shared DARTS cell from the language generated by the CFG from Equation 12
HIERARCHICAL CELL SEARCH SPACE
The hierarchical cell search space (Liu et al. 2018) consists of fixed (linear) macro architecture and a hierarchically assembled cell with three levels which shared across the macro architecture. Thus, can omit the fixed macro architecture from our search space design for simplicity. Their first, second, and third hierarchical levels correspond to the primitive computations (i.e., id, max max_pool, avg-pool, sep_conv, depth.cony conv, zero), six densely connected four node directed acyclic graphs (DAG4), and a densely connected five node directed acyclic graph (DAG5), respec- tively. The operation could lead to directed acyelic graphs which have fewer nodes. Therefore,
19

---

Under review as a conference paper at ICLR 2023
introduce constraint enforcing that there always four (level 2) or five (level 3) nodes for every directed acyclic graph. Further, since a densely connected five node directed acyclic graph graph has ten edges, we need to introduce placeholder variables (i.e., Ml, ... M6) to enforce that only six (possibly) different four node directed acyclic graphs are used, and consequently define a CFG for the third level
LEVEL3 : DAG5 (EEELL2
LEVEL2)
X10
(14)
LEVEL2 = M1
M2
M3
M4
M5
M6
zero
mapping the placeholder variables M1, ... M6 to the six lower-level motifs constructed by the first and second hierarchical level
LEVEL2 == DAG4
LEVELI)
x6
(15)
LEVEL1 == id max.pool avg-pool
sep-conv depth.ccov
conv
zero
MOBILE-NER NET SEARCH SPACE
Factorized hierarchical search spaces, e.g., the Mobile-net search space (Tan al.) 2019), allow for layer diversity. They factorize a (fixed) macro architecture often based on an already well- performing reference architecture into separate blocks (e.g., cells). For the sake of simplicity, we assume here three sequential blocks (Block) architecture (Linear). In each of those blocks, we search for the convolution operations (CONV), kernel sizes (KSIZE), squeeze-and- setree-anddeeiiationn ratio (SERATIO) (Hu et al. 2018). skip connections (SKIP), number of output channels (FSIZE), and number of layers per block (#LAYERS), where the latter two are discretized using a reference architecture, e.g. MobileNetV2 (Sandler et al. 2018). Consequently, we can express this search space as follows:
MACRO Linear(BLOCK, BLOCK, BLOCK)
BLOCK : (CoNV, KSIZE, SERATIO, SKIP, FSIZE, #LAYERS)
CONV :: conv dconv mbconv
KSIZE : 3 3
(16)
SERATIO 0 I 0.25
SKTP pooling | id_residual no_skip
FSIZE := 0.75 1.0 1.25
# #LAYERS :: -1 0
where conv, donv and mbconv correspond to convolution, depthwise convolution, and mobile inverted bottleneck convolution (Sandler et al. 2018), respectively.
HIERARCHICAL RANDOM GRAPH GENERATOR SEARCH SPACE
The hierarchical random graph generator search space (Ru et al. 2020 consists of three hierar- chical levels of random graph generators (i.e., Watts-Strogar Erdös -énbs- (Erdós et al. 1960)). We denote with Patts-Strogaa Sttattooggttii the random graph generated by the Watts-Strogatz model with nodes. Thus, we can represent the search space as follows:
(Watts & Strogatz 1998) and
TOP Watt.s-Strogazz 3KK, PMI(M MID, MID) Watts-Strrogttz_00KK (t)( MID)
x10
MID = (Po00-Réény_11Pm))BBB8
1a8ba-Rényi.100Pmm (BOT, BOT
(17)
x10
BOT Watts-Strogatz.:(KK (NDDE, NODE, NODE)
Stt.Stttrrtttt Pb) (NODE NODE)
x10
K = 2 2 3 5
20

---

Under review as a conference paper at ICLR 2023
Algorithm Bayesian Optimization algorithm (Brochu et al. 2010).
Input: Initial observed data D;, a black-box objective function f. total number of BO iterations
T
Output:
The best recommendation about the global optimizer x"
for 1,..., .T do
Select the next X by maximizing acquisition function ax(x (D.)
Evaluate the objective function at S1+1 [(x+1)
Di+1 f Dr U (x--1: ft+1)
Update the surrogate model with D(+1
end for
where each terminal Pt, Pm, and Pb maps to a continuous number in (0.1, 0.9 and the placeholder variable NODE maps primitive computation, e.g., separable convolution. Note that omit other hyperparameters, such as stage ratio, channel ratio etc., for simplicity.
F MORE DETAILS ON THE SEARCH STRATEGY
In this section, we provide more details and examples for our search strategy Bayesian Optimization for Algebraic Neural Architecture Terms (BANAT) presented in Section 3
F.1 BAYESIAN OPTIMIZATION
Bayesian Optimization (BO) is powerful family of search techniques for finding the global opti- mum of black-box objective problem. It is particularly useful when the objective is expensive to evaluate and thus sample efficiency is highly important (Brochu et al. 2010).
To minimize a black-box objective problem with BO, we first need to build a probabilistic surrogate to model the objective based on the observed data so far. Based the surrogate model, we design an acquisition function evaluate the utility of potential candidate points by trading off exploita- tion (where the posterior mean of the surrogate model is low) and exploration (where the posterior variance of the surrogate model is high). The next candidate points to evaluate is then selected by maximizing the acquisition function (Shahriari et al. 2015). The general procedures of BO is summarized in Algorithm|] [
We adopted the widely used acquisition function, expected improvement (EI) (Mockus al. 1978), in our BO strategy. El evaluates the expected amount of improvement of candidate point x over the minimal value f' observed far. Specifically, denote the improvement function 7(x) ma f' f(x)), the El acquisition function has the form
(EI(x|(.) [((()) ('' (IWNI)))))) df = -) (x)) + (
((x(D)))
where ((x[D;) and o² (x) are the mean and variance of the predictive posterior distribution at candidate point x, and (b.) and (..) denote the PDF and CDF of the standard normal distribution, respectively.
To make use of ample distributed computing resource, we adopted Kriging Believer (Ginshourger al. 2010) which uses the predictive posterior of the surrogate model to assign hallucinated func- tion values {fp) (.p)pe(1.... pj to the P candidate points with pending evaluations (8p)pt{1, P) and perform next BO recommendation in the batch by pseudo- augundiingg the observation data with Dp = {xxp fp) pe)) py. namely D, = D, D.p The algorithm of Kriging Believer at one BO iteration to select batch of recommended candidate points is summarized in Algorithm
"Theoretically. this is not possible with CFGs. However, extend the notion of substitution by substi- tuting string representation of Python (float) variable for the placeholder variables Pt, Pm, and Pb.
21

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Kriging Believer algorithm to select one batch of points.
Input: Observation data P;, batch size
Output: The batch points B = {x x x
D. D, DD,
for j = -.......,bbb do
Select the next x by maximizing acquisition function axx (D))
Compute the predictive posterior mean ((x4111D))
D. + De (xx+1: ((1411DD))) end for
Algorithm& 3 Weisfeiler-Lehman subtree kernel computation (Shervashidze et al. 2011).
Input: Graphs G1, G2, maximum iterations H
Output: Kernel function value between the graphs
Initialize the feature vectors (GG) (o(Gi), (GG2) c with the respective counts of
original node labels (i.e., the h = 0 WL features) for L........ do Assign a multiset (v) = (1)-1(u)lu E N(v)} to each node E G, where 4--1 is the node label function of the 1-th WL. iteration and is the node neighbor function
Sort elements in multiset Mr (v) and concatenate them to string s (v)
Compress each string 8) (v) using the hash function s.t. f(s((v) = f(sx(w))
(v) = (u)
Add 4 as prefix for (v)
Concatenate the WL features d% (G1),, on (G2) with the respective counts of the new labels:
(GG) = = on (G, (GG2) = (o(G2), ; on (G2)
Set 1 (v) = ((s(()) Vu GG
end for
Compute inner product (dn (n (G2)) between WL features on (G1), on (G2) in RKHS H
F.2 HIERARCHICAL WEISFEILER-LEHMAN KERNEL
Inspired by Ru et (202T) we adopted the Weiseeiler-Lehman (WI) graph kernel (Shervashidze) et al., 2011) in the GP surrogate model to handle the graph nature of neural architectures. The basic idea the WL kernel to first compare node labels, and then iteratively aggregate labels of neighboring nodes, compress them into new label and compare them. Algorithm summarizes the WL kernel procedure.
Ru et al. (021)) identified three reasons for using the WL kernel: (1) it is able to compare la- beled and directed graphs of different sizes, (2) it expressive, and (3) it is relatively efficient and scalable. Our search space design afford diverse spectrum of neural architectures with very heterogeneous topological structure. Therefore, reason (1) is very important property of the WL kernel to account for the diversity of neural architectures. Moreover, if we allow many hier- archical levels, we can construct very large neural architectures. Therefore, reasons (2) and (3) are essential for accurate and fast modeling. However, neural architectures in our search spaces may be significantly larger, which makes it difficult for single WL kernel to capture the more global topological patterns. Moreover, modeling solely based on the final neural architecture ignores the useful macro-level information from earlier hierarchical levels. In our experiments (Section 5 and T}. we have found stronger neural architectures by incorporating the hierarchical information in the kernel design, which provides experimental support for above arguments.
However, modeling solely based on the (standard) WL graph kernel neglects the useful hierarchical information from our assembly process. Moreover, the large size of neural architectures make it still challenging to capture the more global topological patterns. We therefore propose to use hierarchical information through hierarchy of WL graph kernels that take into account the different granularities of the architectures and combine them in a weighted sum. To obtain the different granularities, we the fold operators F; that removes algehraic terms beyond the l-th hierarchical level. Thereby,
22

---

Under review as a conference paper at ICLR 2023
id
id
cony con onny fc
(a) (w) (RnearrRessde (aaaaaraeeeeaaaaaaeaaaaaaaaaaaa duallcoov,, id, conv), Residual(conv, id, conv), fc).
Residua Residual fc
(b) (2) Linear(ResiduaL. Residual, fc).
Figure Labeled graphs (F2) and @ of the folds F2 and F3-
obtain the folds
(w(w) w = Linear(Resiiuul id, conv), Residual id, conv), fc),
(18)
(2(w) = Linear(Residual. Residual, fc) Fi(w) Linear
for the algebraic architecture term w. Note that we ignore the first fold since it does not represent labeled DAG. Figure visualizes the labeled graphs ((F2) and ( of the folds F22 F3, respectively. These graphs can be fed into (standard) WL graph kernels. Therefore, we can construct hierarchy of WL graph kernels kwL follows:
kwwL(Wis wyy) = A kw- (. (
(19)
2
where w, and wj two algebraic architecture terms. Note that X govern the importance of the learned graph information across the hierarchical levels and can be optimized through the marginal likelihood.
F.3 EXAMPLES FOR THE EVOLUTIONARY OPERATIONS
For the evolutionary operations, we adopted ideas from grammar-based genetic programming (McKay al., 2010 Moss al.) 2020). In the following, we will show how these evolutionary operations manipulate algebraic terms, e.g.,
Linear (Res dual(conv, id, conv), Residual(conv, id, conv), fc)
(20)
from the search space
S ::= Linear(S, S, S) Residual(S, S, S) conv id fc
(21)
to generate evolved algebraic terms. Figure I shows how can derive the algebraic term in Equa-
tion 20 from the search space in Equation 21 For mutation operations, we first randomly pick subterm of the algebraic term, e.g., Residual (conv, id, conv). Then, we randomly sample new subterm with the same nonterminal symbol S as start symbol, c.g., Linear(conv, id, fc), and replace the previous subterm, yielding
Lineer(LLneax:
1d, fc), Res Residual id, conv), fc)
(22)
For (self--crrossover operations, swap two subterms, e.g., Residual (conv, id, conv) and Res desidual (conv, id, conv) with the same nonterminal S as start symbol, yielding
(iiear(Residuall)
id, conv), Residual(conv, id, conv), fc)
(23)
Note that unlike the commonly used crossover operation, which uses two parents, self-crossover has only one parent. In future work, we could also add self-copy operation that copies subterm to another part of the algebraic term, explicitly regularizing diversity and thus potentially speeding up the search.
G RELATED WORK BEYOND NEURAL ARCHITECTURE SEARCH
While work focuses exclusively on NAS, will discuss below how it relates to the areas of optimizer search (as well as from scratch automated machine learning) and neural-symbolic pro- gramming.
23

---

Under review as a conference paper at ICLR 2023
Optimizer search is closely related field to NAS, where we automatically search for optimizer (i.e., an update function for the weights) instead of an architecture. Initial works used learnable parametric non-parametric optimizers. While the former approaches (Andrychowicz et al. 2016
[i & Malik 2017 Chen et al.) 2017; 2022a) have poor scalability and generality, the latter works overcome those limitations. [Bello et al. (2017) searched for an instantiation of hand-crafted patterns via reinforcement learning, while Wang et al. (2022) proposed a tree-structured search spacd? and searched for optimizers a modified Monte Carlo sampling approach. AutoML-Zero (Real al. 2020) took an even more general approach by searching over entire machine learning algorithms, including optimizers, from generic search space built from basic mathematical operations with an evolutionary algorithm. [Cen et al. (2022b) used RE to discover optimizers from a generic search space (inspired by AutoMI.-Zero) for training vision transformers (Dosovitskiy et al. 202T).
Complementary to the above, there is recent interest in automatically synthesizing programs from domain-specific languages. [Gaunt et al. (017)) proposed hand-crafted program template and si- multaneously optimized the parameters of the differentiable program with gradient descent. The HOUDINI framework (Valkov et al. 2018) proposed type-directed (top-down) enumeration and evolution approaches over differentiable functional programs. Shah et al. (2020) hierarchically sembled differentiable programs and used neural networks for the approximation of missing expres- sion in partial programs. Cui & Zhu (202T) treated CFGs stochastically with trainable production rule sampling weights, which were optimized with a gradient-based approach (Liu et al.] 2019b). However, naively applying gradient-based approaches does not work in our search spaces due the exponential explosion of supernet weights, but still renders an interesting direction for future work.
Compared to these lines of work, we extended CFGs to handle changes in spatial resolution, promote regularity, and (compared to most of them) incorporate constraints, the latter two of which could also be applied in those domains. We also proposed BO search strategy search efficiently with a tailored kernel design to handle the hierarchical nature of the search space (i.e., the architectures).
H IMPLEMENTATION DETAILS OF THE SEARCH STRATEGIES
BANAT & BANAT (WL) The only difference between BANAT and BANAT (WL) is that the former uses our proposed hierarchy of WL kernels (h (h),), whereas the latter only uses single WL kernel (WL) for the entire architecture (c.f., (Ru et al. 202I)). We ran BANAT asynchronously in parallel throughout single architecture is proposed for evaluation. For the acquisition function optimization, we used pool size of P 200, where the initial population consisted of the current ten perf-pernogning architectures and the remainder were randomly sampled architectures to encourage exploration in the huge search spaces. During evolution, the mutation probability was set Prout 0.5 and crossover probability was set to Peross = 0.5. From the crossovers, half of them were self-crossovers of one parent and the other half were common crossovers between two parents. The tournament selection probability was set to Ptour 0.2. We evolved the population at least for ten iterations and a maximum of 50 iterations using a early stopping criterion based on the fitness value improvements over the last five iterations.
experiments with batch size of B 1, i.c., at each BO iteration
Regularized Evolution (RE) RE RReal et al. 2019 Liu et al. 2018 iteratively mutates the best architectures out of sample of the population. We reduced the population size from 50 to 30 to account for fewer evaluations, and used sample size of 10. We also ran RE asynchronously for better comparability.
I SEARCHING THE HIERARCHICAL
SEARCH SPACE
In this section, we provide training details (Section I.I] and provide complementary results as well as conduct extensive analyses (Section] I.2)
Note that the tree-structured search space can equivalently be described with CFG (with constraint on the number of maximum depth of the syntax trees).
24

---

Under review as a conference paper at ICLR 2023
Table Licenses for the datasets we used in our experiments.
Dataset
License
URL
CIFAR-10
Krizhevsky et al.
2009
MIT
Loronto......o.................. wwwponttt...ueeeeeooooooo -wsia//kri/ciaaaaa htt.
CIFAR-100
Knzhevsky et 2009
MIT
nEtDS://WW. Eoronto 600/ wtw.///aaa..aattatttt.
ImageNet-16l
6-120 (Chrabaszzz et 2017
MIT
github 10/ Imagenet
CIEARTile
Geada el ul. 2021
GNU
https://q httpeeass/sstt-ooaaeeoo nastta datasets
AddNIST
Ieada
GNU
https:77gsthuz, wttpc///wo.oaaapapraaaaaaaa-a-ea
1.1 TRAINING DETAILS
Training protocol We evaluated all search strategies CIFAR-10/100 (Krizhevsky al. 2009),
AmageNet-16-122) (Chrabaszez et al.] 2017), CIFARTile, and AddNIST (Geada et al., [202]) Note that CIFARTile and AddNIST novel datasets and therefore have not yet been optimized by the research community. We provide further dataset details below. For training of architectures on CIFAR-10/100 and ImageNet-166 20, we followed Dong & Yang 2020 We trained architectures with SGD with learning rate of 0.1, Nesterov momentum of 0.9, weight decay of 0.0005 with cosine annealing (Loshchilov & Hutter 2019), and batch size of 256 for 200 epochs. The initial channels were set to 16. For both CIFAR-10 10 and CIFAR-100, we used random flip with probability 0.5 followed by a random crop (32x32 with 4 pixel padding) and normalization. For ImageNet-16, 120. we used 16x random crop with 2 pixel padding instead. For training of architectures on AddNIST and CIFARTile, we followed the training protocol from the CVPR-NAS 2021 competition (Geada et al., 202T): We trained architectures with SGD with learning rate of 0.01, momentum of 0.9, and weight decay of 0.0003 with cosine annealing, and batch size of 64 for 64 epochs. We set the initial channels to 16 and did not apply any further data augmentation.
Dataset details In Table 4 we provide the licenses for the datasets used in our experiments. For training of architectures on CIFAR-1O, CIFAR- (Krizhevsky et al. 2009). and maageNet-16-120 followed the dataset splits and training protocol of NAS-Bench-201 (Dong & Yangl 2020). For CIFAR-10, 10. we split the original training set into a new training set with 25k images and validation set with 25k images following Dong & Yang (2020). The test set remained unchanged. For evaluation, we trained architectures on both the training and validation set. For CIFAR-100, the training set remained unchanged, but the test set was partitioned in a validation set and new test set with each 5K images. For ImageNet- For AddNIST and CIFARTile, we used the training, validation, and test splits as defined in the CVPR-NAS 2021 competition (Geada et al. (021).
(Chrabsszzz al. 2017).
all splits remained unchanged.
1.2 EXTENDED SEARCH RESULTS AND ANALYSES
Supplementary Figure 2 Figure compares the cell-based vs. hierarchical NAS-Bench-201 search space from Section 6.1 using RS, RE, and BANAT (WL). The cell-based search space de- sign shows on par or stronger performance on all datasets except for CIFARTile for the three search strategies. In contrast, for our proposed search strategy BANAT we find on par (CIFAR-10/101 or superior (ImageNet-16-1200 CIFARTile, and AddNIST) performance using the hierarchical search space design. This clearly shows that the increase of the search space does not necessarily yields the discovery of stronger neural architectures. Further, it exemplifies the importance of a strong search strategy to search effectively and efficiently in huge hierarchical search spaces (Q2), and provides further evidence that the incorporation of hierarchical information efficiency (Q3). Based on this, believe that future work using, e.g., graph neural networks surrogate, may benefit from the incorporation of hierarchical information.
key contributor for search
We report the test errors of our best found architectures in Table 5 strategy BANAT finds the strongest performing architectures across all dataset (Q2, Q3). Also note that we achieve better (validation and) test performance on ImageNet- 16- 120 on the hierarchical than the state-of-the-an search strategy on the cell-based XAS-Bench search space (i.e., +0.37%p compared to Shapley-NAS (Xiao et al. 2022 (Q1).
We observe that our search
25

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CTFAR-100
ImageNet-16-122
CTile
AddNIST
Val error [%)]
32
66
04
62
25
50
75
100
25
50
75
100
25
50
75
100
25
50
75 100
25
50
75
100
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
hierarchical
rell-based
Random Search (RS).
CIFAR-10
CIFAR-100
ManageNet-16--11
CIFARTile
AddNIST
Val error [%)]
32
66
04
62
25
50
75
100
25
50
75
100
25
50
75
100
25
50
75 100
25
50
75
100
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
hierarchical
cell-based
(h) Regularized Evolution (RF).
CIFAR-10
CIFAR-100
ImageNet-166
CIFARTile
AddNIST
Val error [%)]
322
56
64
26
62
25
50 75
100
25
50
75
100
25
50
75
100
25 50 75 100
25 50 75 100
Evaluations
Evaluations
Evaluations (c) BANAT (WI.).
Evaluations
Evaluations
hierarchical
cell-based
Figure 8: Cell-based vs. hierarchical search spaces. We plot mean and +1 standard error of the validation emoor on the cell-based (dashed orange) and hierarchical (solid blue) NAS-Bench-200 search space using Random Search (RS) (top). Regularized Evolution (RE) (middle), and BANAT (WL) (bottom).
26

---

Under review as a conference paper at ICLR 2023
Table 5: Test errors (and +1 standard error) of popular bascline architectures (c.g., ResNet (He et al. 2016) and EfficientNet (Tan & Le 2019) variants), and our
best found architectures on the ball- and hierarchical NAS Bench-2nch -201 search space. Note that we picked the ResNet and EfficienNeet variant based on the test error, consequently giving overestimate of their test performance. optimal numbers as reported in Dong & Yang 2020)
hiceachhica
1:0:000. 0.29
11.81 : 1.55
14.47 4 1.44
13.57 1 1.89
14.82 0.66
7.56 7 0.09
8.2 1 0.37
6.09 0.34
6.33 1: 0.59
7,78 1: 0.05 (34)
13:24 0.58 (B
8.05
AddNIST
(best) test error (and #1 standard error) across (hree seeds (777, 888, 999) } of the best architecture of the three search rums lowest validation error.
cell- all-bbsed
7.82 # 0.36
0.69
10.75 4 0.23
10.68 9: 0.27
0.53
1 0.35
7.86 1 0.41
7,86 0.41
8.04 11 0.45
10.1
10.72
7.69
hierachical
40.93 + 0811
2.95
43.31 2.0
1 1.29
0.67
40 99.99 2.89
35.75 1 1.58
2.39
1 0.77
57.8 1: 0.57 (18)
61.01 0.62 (BO)
49.46
42.45
32
30.33
CIFARTle
45
ocll cell- bllbbased
52.72 + 0.45
2.29
41.63 1 1.02
39.61 1 1.12
1.2
02.79:0.50 0.59
52,81 1 0.27
52.81 #: 0.27
53.18 1: 0.91
41.83
39.9
52.79
hierurchical
34.7 0.82
0.29
2.74
4 0.91
1.53
0,54
51.47 4 0.86
0.61
52.78 1: 0.23
ImageNer- 16- 120
$3.67 1 0.18 (56) 77.73 0.29 (B0)
38.66
58
57.58
55 39
53.43
58
52.69
cell-bused
54.33 + 0.78
1.35
1.3
1 2.92
0,49
1 0.39
1 0.39
0.43
0.43
53.54
56.8
55.99
58.93
54.2
53.92
53.67
53.67
hicrarchical
29.49 0.51
4 1.95
4 0.72
+ 1.61
20.0 0.32
1 0.64
27.57 : 0.46
27.6310..2 0.2
27.1 1: 0.67 (110) 35.17 + 0.42 (B6)
31.73
31 65
31 66
32.09
27.63
CIFAR 100
28.7
26.49
col lll-based
+ 0.57
0.53
0.25
0
0.42
0.53
1 0.18
0.18
d 0.23
28.75
29.35
28.91
29.37
20.95
27.08
27 27.66
27.66
27.03
hieruchical
1:100.11 0.1
0.46
156::000 0.87
1 0.38
+ 0.52
0.24
0.5
+ 0.16
5.65 1 0.09
6.49 1: 0.24 0.24 (32)
11.73 0.1 (BO)
0.88100
CIFAR- 10
6.77
8.18
8.56
8.26
6,88
6.98
6.0
5.63
cell- bl-ebed
0.18
6.55 0.1
6.59 0.17
6.68 1012
0.43
5.76 0.17
0.11
0.11
5.64 0.14 0.14
6.39
6.98
5.68
5.68
Mellor C al 2022
20211
Mellor di of 202
Liu 2018
Best EfficicuNNet Ban & Le 2019
Mellor et al.
Best ResNei [Tle el al 2016
Meller
BANAY NATT (ANATWLL) (WL) Ru ct m MIZ2
NAS- Bench-Bnn111 oracle
NASWOT (N- 100)
NASWOT 10100
NASWOL (N= 10000
RE Real 2019
NASWOI (N=10)
BANAT (best)
Method
BANAT
RS
27

---

Under review as a conference paper at ICLR 2023
CTFAR-10
CTFAR-100
ImageNet-10 16-120
CIFARTile
AddNIST
20
50
55
30
75
40
10
50
BANAT
[ouns)
B8
RE
BANAT
(WL
BANAT
(ouna) I8S
82
(W1)
BANAT
(ours)
R8
RE
BANAT
(W1)
(once)
nR R5
BANAT
[ouro)
B8
RB
DANAT
(WD)
Figure 9: Density estimates for the validation error of all architecture candidates proposed by the
search strategies (i.e., BANAT, RS, RE, and BANAT (WL)) and across datasets (i.e., CIFAR-10/100,
MaageNet-16-1200 CIFARTile, AddNIST) from our experiments in Section 5
Search costs Search time varied across datasets from ca. 0.5 days (CIFAR-10 10) to ca. 1.8 days (ImageNet-16-12) 120) using eight asynchronous workers, each with an NVIDIA RTX 2080 Ti GPU, for ca. 4 to ca. 14.4 GPU days in total.
Is our search strategy BANAT exploring well-performing architectures during search? To investigate the question, we studied density estimates of the validation error of proposed candidates for all search strategies across our experiments from Section 5 This provides a better view for whether search strategies are exploring -erl-pernggning architectures or wasting computational re- shows that our proposed search strategy BANAT explored better architecture candidates across all the datasets, i.e., it has smaller median validation errors and the distributions are further shifted towards smaller validation errors than for the other search strategies.
sources on low-performing architectures. Figure 9
What distinguishes top-performing neural architectures from the other ones? To understand what distinguishes perfforrnmng neural architecture from other ones, we analyze the impact of maximum depth on performance and the frequency of production rules in the worst-105% 10%, top- 100, the validation
other neural architectures, respectively. In another analysis, error of every production rule; thereby relating the contribution of a production rule with the per- formance of the architecture. Note, however, that both analyses ignore the topological information, i.e., topological operator or primitive computation may have a different effect at different stages of the architecture.
marginalize
Figure 10 shows no particular trend (e.g., more depth yields better performance) across the datasets, indicating that depth may not be the most important factor for performance in our hierarchical search space. In contrast, Figure and Figure 12 show that particularly macro-level production rules (i.e., for the nonterminals D2, DI, DO, and D) have a large effect on the performance of an architecture. Interestingly, we find that that top-performing architectures (almost exclusively) use the topological operator Res dual3 for derivations from the nonterminal D1 across search spaces, This hints that residual connection the macro-level could be strong topological structure, but remains to be evaluated for a variety of architectures. Cell-level production choices have less effect on performance. However, hypothesize that this may also be due to the neglect of topological information. We leave further analysis for future work.
What is the impact of flexible parameterization of convolutional blocks? To investigate the im- pact of the flexible parameterization of the convolutional blocks (i.e., activation functions, normal- izations. and type of convolution), we removed the flexible parameterization and allowed only the MAS-Bench-2011 search space. while still search-
same primitive computations as in the cell-based ing over the macro architecture. More explicitly, we only allow ReL.U non-linearity as the activation function, batch normalization as the normalization, and 1 x 1 or 3 x 3 convolutions. Figure [3] shows that for all datasets except CIFAR- flexible parameterization of the convolutional blocks improves performance of the found architectures. Interestingly, we find architecture CIFAR- 100, which achieves 26.24 % test error with 1.307 MB and 167. 167.172N M number of parameters or FLOPs, respectively. This architecture is superior to the optimal architecture in the cell-based NAS- Bench-201 search space. Note that this architecture is also pareto-optimal for test error vs. number of parameters and test error number of FLOPs.
28

---

Under review as a conference paper at ICLR 2023
CIFAR-10
C-
MengeNet-11-1222
CIFARTile
AddNIST
Val error [%]]
20
40
70
60
20
15
35
50
15
40
10
30
30
10
50
100
200
100
200
100
200
100
200
100
200
Depth
Depth
Depth
Depth
Depth
Worst-10%
Other
Top-10%
Best
Figure 10: Validation error over maximal depth of all architecture candidates proposed by the search strategies (i.e., BANAT, RS, RE, and BANAT (WL)) and across datasets (i.e., ImageNet- 16-120, CIFARTile, AddNIST) from our experiments in Section 5
Test error vs. number of parameters and FLOPs Figure 14 shows the test error vs. the number of parameters or FLOPs. Our best found architectures fall well within the parameter and FLOPs ranges of the cell-based NAS-Bench-25 on CIFAR-10 10. Note that our best found architecture on ImageNet- 16-tt-161111 120 is pareto-optimal for test error number of parameters and test error number of FLOPs.
search space across all datasets, except for the parameters
Best architectures Below we report the best found architecture per dataset on the hicrarchical NAS-Bench-201 search space (Section [.T] for each dataset. Figure 13 visualizes the novel and diverse design of the architectures (including stem and classifier head).
CIFAR-10 (mean test error 5.65 %, #params 2.204 MB, FLOPs 127.673 M):
zero, Linear (Lincar3hhardswissh, convlx Ix1, layer)), Linear (harssshh conv3x3, layer)), zero, ( conv3x3, instance))), Cell[_inear(LLinerreeeee dconv3x3, layer)), id, avg-pool, Lin- ear carl(Linear3rrelu, dconv3x3, layer)), id, zero), Cell(zero, Linear (Iinear3(.nn convixl, layer)), id, Linear (Linerrr convix1, instance)), Linearl ([innar3 conv3x3, layer)), Linearl (Lineere(Lnaaaaarsssiiii dconv3x3, layer)))), Residuall(Cell(dd, zero, Linear (anearl(Linear]3a (Linear3(relu, cxl. layer)). Linearl ( layer)), Linearl (Lineaar(LLineashhadssswsll conv3x3, layer)). zero). Cell(id, zero, id, (ineaaaarn.inaaaaaaaaarriiii
convlx1,
conv3x3, batch)), id, conv3x3, layer)), Lincar| (aatrllLLnnncn ([incar3(hardswwish convixl, layer)), Lincarl (I Lincar3(relu, convixl, layer)), Linear (I (rrhaa conv3x3, layer)), zero, id)) Resid- Ial2(Ceil(Linear| (L (hardswwsh,, cxl, instance)). dconv3x3, batch)), Linear Linearl (Linear3(mish, dconv3x3, instance)). Linearl I ((rnear3(relu, convix1, batch)), id, id), down, down), Residual2(Cell(LLnne) (Linear convixl, layer)), Lincarl (Laaaaan dconv3x3, batch)), Lincarl (Lincar3 convixl, batch)), Linearl (Linaar((LLinna33haaswssss conv3x3, layer)), id, avg-pool), down, down)).
zero, Linearl (Liearr(wiinarhhhadswwwssl layer)). Linearl ([neaaa(iiinarrhhrdssstttt conv3x3, layer)). id, Linearl ( conv3x3, instance))). Cell([.nnea) (Iiinar33rrllu, dconv3x3, layer)), id, avg-pool, Lin- earl carl(L.inur33reeu, dconv3x3, layer)), id, zero), Cell(zero, Linearl(I.neear.] (Iinnar3(relu, 1x1, layer)), id, (hinerr((Linear(hardsvviiiii cxnv layer)). Linear ( (Linear3(hardswisk) deonv3x3, layer)))). Residual2(Celllid, zero. (
conv 1x1,
convlx1, instance)). Linear ( (haress((a
Ix1, layer)), Linearl (Linear33nii conv3x3, layer)), Lin- car carl(Linnar3(harddiiss dconv3x3, batch)), zero), Cell(id, zero, id, (Lincar3ri,,, conv3x3, layer)), Lin-
conv3x3, batch)), id, id), (ha@hinhear convlxl, layer)), Linear I (mis,,r3(mishh, cxlv batch)), Lin- carl (Linearrar,,,,,,,, conv3x3, imstance)), zero, id)), Residual|2(Cll((inenn (Lincarr(ina dconv3x3 batch)), id, Linearl (Iinear3
conv 1x1, batch)), Linear Siteeal(Liing ([ convixl, batch)), id, id), down, down), Residual2(CelllLinena) (harsws. convixl, layer)), Linearl (harshhhhahahhr dconv3x3, batch),, Linearl (re,,, convixl, batch)), Linearl (Lieaal(Liiear3(haarssssshh conv3x3, layer)), id, avg pool), down, down)), Linears(Rssiduul(CCCllLiii.. (Linear3(hardsswis)) conv3x3, batch)), Lin- ear (Lineerar3(rr,,, convixl. instance)). Linearl (rrnear3(relu, convixl, layer)), Linearl (Iinearr.in,,,,,,cllu convixl, layer)), Linearl (L_inear33ee convixl, layer)), id), Cell(Linear [al[[iinerr(..inea33rreee (Ineaa,3rr,, convix1, batch)), id, id, Linearl innear33rel,,
29

---

Under review as a conference paper at ICLR 2023
Worst-10%
Other
Top-10%
CIFAR-10
CIFAR-100
Image Net-16-120
CIFARTile
AddNIST
Proportion
1.0
1.0
1.0
1.0
1.0
0.0
0.9
0.0
0.0
0.0
Lioear3
Linear[(DC
Linoard
Lioc S(D1
Linmerd
Linear
Linear
Lineary
Limerr
Einear3
Lineard
Lioca BIDD
(a) D2 =
(D1, D1, DO)
(Do, D1, D1)
Linear4(DI, D1, DO, DO).
1.0
1.0
1.0
1.0
1.0
Proportion
Eionard
Linoard
Rosiduats
Lincard
Linosed
Rowidunds
Liooard
Linesed
Roeldusto
Linowrs
Linewed
Reelduuld
Eincara
Llocord
Residal8
(b) D1 =
Linear3(C, C, D)
Linear4 C, C, D)
Residua13(C, C, D, D).
Proportion
1.0
1.0
1.0
1.0
00
Lioeara
Lineard
Roaduals
Liveur
Lineurd
Roodhaal
Lipears
Linesed
Rendualy
Reddualt
Lioear
Liocar
(c) DO
(Cnear3(C, C, CL)
Linear4 C, C, CL)
(esidual3(C,, C, CL, CL).
Proportion
1.0
1.0
0.5
0.5
0.5
D10
0.0
0.0
0.0
D.0
Libowr2
Linear
Residua12
Linowr2
Liuour8
Residini22
Linour2
Linenrt
Renidusip
Linowr2
Limowra
Residins12
Litear2
Libeara
Residum
D Linear2(CL, down)
Linear3(CI.. CL. down)
Residual2(C, down, down).
Proportion
0.5
0.5
0.5
0.5
0.5
0.9
0.0
0.0
0.0
Lineara
Lineara
Residual2
Linoar
Lincar
Reaidwal2
Linear2
Lineard
Restdualz
Ninera
Reddhall2
Linear2
Lineara
Residual
(e)
=
Linear2(CI, CL)
Linear3(CL, CL)
Residual2(CL, CL, CL).
Proportion
1.0
1.0
0.5
0.5
0.5
0.5
0.5
BLOCK
698 pool
5020
BLOCK
2Y8 po0l
BLOCK
20g pool
BLOCK
WV p000
BLOCK
0YA p00)
(f) OP
zero
idd BLOCK
avg_pool.
30

---

Under review as a conference paper at ICLR 2023
Worst-10%
Other
Top-10%
CIFAR-10
CIFAR-100
CIFARTile
AddNIST
Proportion
1.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.5
0.0
0.0
0.0
rolu
rolu
rolu
melu
hardbaeth
bardowiall
(g) ACT
rolu
hardswish mish.
1.0
1.0
1.0
1.0
1.0
Proportion
0.0
0.0
0.0
0.0
0.0
cooVEx
deouv3e3
couvist
CODY EX
20097 Ex1
(h) CONV
convix1
conv3x3
dconv3x3.
1.00
1.00
1.00
1.00
1.00
Proportion
0.76
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
0.00
buteh
byer
tayor
bayoz
NORM
batch
instance
Layer.
Figure 11: Comparison of the proportion of production rules in the worst- (blue), top- 10%
(green) and other (orange) neural architectures from our experiments in Section 5
31

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CIFAR-100
ImageNet-16-120
CIFARTile
AddNIST
axrox (98)
100
100
50
80
20
50
25
Linear3 2
10
Linowrd
Liucar3(p)
Linear3
Libeard
Linear
Lnneara
Limcurd
Linears
Lioear3(DD
Limour
Linear
Liuear3(DD
(a) D2
=
Linear3(DI, D1, DO)
Linear3(D0, D1, D1)
Linear4(DI, D1, DO, DO).
100
100
oreon (98]
25
30
50
20
25
60
10
L/nea33
Linor4
Residual5
Liueaz
Linmar
Rosidudl
Linoz2
Linertt
Residuis
Limmer
Lineazt
Bosidull
Linexd
L/noxt
Readuall
(b) D1
=:=
Linear3(C, C, D) dinear4(C, C, C, D) Residua13(C, C, D, D).
100
2
aroor
50
80
25
10
Monew
Lioeure
Redduula
Litcouc
Lineers
Residul3
Lioeus
Libeace
Readuat8
Linenrs
Libears
Besduals
Lionace
Beadusts
(c) DO =
Linear3(C, C, CL)
Linear4(C, C, C, CL)
Residual 3(C, C, CL, CL).
100
30
30
80
40
60
Linea3
Resiuaa22
Linear2
Limoerd
Resiuu122
Linear2
Lineard
Roadua2
Lanar2
Lineera
Resdua22
Lomerr2
Lineara
Rondua22
(d)
LCCe down)
Linear3(CL) CL, down)
Residual2(C, down, down).
100
100
esror [S8)
60
30
60
20
25
60
Linoor2
Linear3
Reeldhol2
Lincar2
Linoer
Residual2
Linear2
Lineara
Resida122
Linea22
Liocar
Residual2
Linea22
Lincara
Reatdual2
(e) C = Linear2 CL)
Linear3(CL) CL)
Residual2(CL, CL, CL).
100
100
28
Val areox
30
80
20
10
1000
BLOCK
WVE pood
BLOCK
ove pool
BLOCK
BLOCK
wig. pool
ang
(f) OP
zero
id BL.OC avg pool.
32

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CIFAR-100
ImageNet- Not-16-12000
CIFARTile
AddNIST
73
50
80
20
25
10
3020
relu
madh
gg) ACT
relu
hardswish
mish.
100
100
30
58
20
25
60
conv2. 1x]
conoak3
Conv3x0
cone1s
(h) CONV
convixl
conv3x3
dconv3x3.
100
100
12
68
80
225
60
10
bask soce
leyer
baxch
Instance
batch
hover
Inttance
NORM ::
batch instance
layer.
Figure 12: Marginalized performance of every production rule in our hierarchical search space from Section
CIFAR-10
CIFAR-100
EmageNNet-66-122
CIFARTile
AddNIST
Val error [%
40
Evaluations
Evaluations
Evaluations
Evaluations
Evaluations
hierarchical
hierarchical without flexible parameterization
Figure 13: Impact flexible parameterization of convolutional blocks in the hierarchical NAS- Bench-201 search space.
33

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CIFAR-100
ImageNet-16-11
Test. error [%]
100
100
100
75
50
80
50
25
60
26
0.2
1.2
2.2
0.2
0.9
1.6
0.2
0.9
1.6
# #params [MB]
# paaaams [MB]
# params [MB]
all cells
best cell
ours
(a) Test vs. number of parameters (#params (MB)).
Test error [%]
CIFAR-10
CIFAR-100
ImageNet-166 1ct-16-12-0000
100
100
75
90
70
50
100
200
100
200
20
40
60
FLOPSs [M]
#FLOPs [M]
#LLOPs [M]
all cells
best cell
ours
(b) Test error vs. number of FLOPs (#FLOPs (M)).
Figure 14: Test error vs. number of parameters (a) and FLOPs (b) for each architecture candidate in the cell-based search space (blue dots), the best cell (orange cross), and our best found architecture (green star).
convixl, layer)), id, id), Cell(id, Linear((Linear3rrhh) convixl, instance)), Lin- ear (Liieerr3rrl,, convixl, instance)), ear (hanswss conv3x3, batch)))), Residual2(Cell(Linear CassiaaaZZCcllinneeeeaaaaaaaaaa conv3x3, layer)), Linearl (Linear3(relu, conv3x3, instance)). Linear I 3 convix1. 1x1, layer)). Linear (Linearr3relu, convlx1, layer)), Linearl (Liner33 conv3x3, layer)), id), Cell(Linear ( (Linear3(relu, convixl, batch)), id, id, Linearl (Lincar3(relu, conv3x3, batch)), id, id), Cell(id, Linearl (Lincar3(relu, convix1, instance)), Lin- ear (Lineeraar3rrl,,, convixl, instance)), Linearl (Lincar333er dconv3x3, layer)), zero, dconv3x3, layer)))), Cell(I.nearr [ (Irinea33rell,, dconv3x3, instance)), zero, zero, id, zero, id)), Linearr(Residuaa2((Clllll (inearl (I 3 conv3x3, layer)), Linearl iinear3(relu, conv3x3. layer)), Linear I 3rnerr3relu, conv 1x1, layer)). Linear 1 (Linear3(relu,, convlx1, layer)). (Linarr conv3x3, layer)), id), Cell(Linear (Linear3(relu convixl, batch)). id. id, Linearl (Linear3(relu, conv3x3, batch)), id, id). Cell(id, Linear (Lenear3(relu, convixl, instance)). Lin- earl (Linerrrrrrr,,,,, convixl, instance)), Lincar I (Lincar3(relu, convix1, layer)), zero, Lin- car (hadswear conv3x3, batch))),, conv3x3, layer)), Lincar (Lincar3(relu, conv3x3, layer)), Lincarl (rrlc, conv 111, layer)), Linear (relu, convlx1, layer)), Linearl layer)), id), Cell(Linearl (Linear3(relu,, convix1, batch)), id, id, Linearl (relu, conv3x3, batch)), id, id), Cell(id, Linearl (Iinear3(relu, convixl, instance)). Lin- car (Linearrr3(r,,, conv 1x1, instance)), L (Linear3(relu, conv 1o1, layer)), zero, Lin- ear ( conv3x3, layer))), Residual((Cell(Lnnean (Lineeaaraannnnaaa 3 conv3x3, layer)). Linear (Lenear3.... conv3x3, layer)). Linear 1 (relu, convixl, layer)),
convix1, layer)), zero, Lin-
conv3x3,
convlx1, layer)), [ conv3x3, layer)), id), Cell([.inearl] (I.nnear3(reluu, convixl, batch)), id, id, Linearl (I (rnearr3rrel,, conv3x3, batch)), id, id), Cell(id, Linearl (Iincar3(relu, convixl, instance)). Lin- ear ((Linear3(relu, convixl, instance)). (Linear[[inaaa3haaaaddae
conv convix1, layer)). zero, conv3x3, layer)))). Cell(id, Linearl (Linarr(LLnaaattattsswssss conv 1x1, layer)), Linear (Linear((i conv lx1, batch)), id, zero, id)))
CIFAR-100 (mean test error 27.63 %, #params 0.962 MB, FL.PPs 115.243 M):
34

---

Under review as a conference paper at ICLR 2023
conv3x3. layer). avg-pool, Lin- (arddhasswish,, convixl, instance), zero, Linear3(mish, conv3x3, batch), zero), CelliLinnar dconv3x3, batch), zero, Lincar3(hardswish, dconv3x3, batch), Lincar3 dconv3x3, batch), id, id), Cell(Lincar3(mish, conv3x3, batch), zero, id, zero, Lhadwr3h,arkwiihh, dconv3x3, batch), id)) Linear2(Cell(id, zero, Lin- ear3(mish, conv3x3, batch), zero, zero, Linsar3(mish, convixl, batch)), Cell(zero, zero, zero, id, zero, avg wyg.o,ol),, Cell(Linnear3rrlu, conv3x3, batch), zero, Lin- car3(harsswish, conv3x3, instance). id, id, avg pool), Cell(id, id. zero, zero, id, id)),
conv3x3, layer). id, whaeashhhrddswihh dconv3x3, layer), Lhadswshhardswish,, dconv3x3, batch). Linh, conv3x3, in- stance), Linear3(mish, conv3x3, batch)), Cell(_.nnear3hhardsviii id, Lhaear3(hardswish, dconv3x3, batch), Lieear3(relu, conv3x3, layer), id, id), Cell Cell(,.incarrrrllu, conv3x3, instance), zero, id, zero, (mish conv3x3, batch), avg pool)), LCelar3 id, Linear3hhardswish, convix1, layer), (mish, conv3x3, instance). Linear3(mish, conv3x3, instance), zero), Chll(Linear3(hardssishh. convixl, layer). id, Lhadssh deonv3x3, batch), Linear3(relu, conv3x3, batch), id, id), Cell(Linear3rehu, conv3x3, instance), zero, id, zero, Linsar3(mish, conv3x3, layer), avg-pool)). Residual2(Celllzeo,, id, zero, Lincar3(mish, conv3x3, layer), avg-pool, Linear3(mish, conv3x3, layer)), down, down). Residual2/Celllzzro,, id, zero, (mih, conv3x3, batch), avg-pool, Linear3(mish, conv3x3, layer)), down, down)), (ieaaal((
convixl, layer),
conv3x3, layer), id, Linnar3(harsswish, dconv3x3, layer). (harssshh dconv3x3, hatch). Linsar3(mish, conv3x3, in- stance), Linsar3(mish, conv3x3, batch)). CellLinnerr(barrdsishh convixl, layer). id. Lhaearrhhardswishh deonv3x3. batch), Linear3(relu, conv3x3, layer), id, id), 3 conv3x3, instance), zero, id, zero, Linear3(mish,, conv3x3, batch), avg avg-pool)), Linear3(Cell(Linnar3mm) conv3x3, batch), id, Linsar3hhardswishh convixl, batch), (mish, conv3x3, instance), Lincar3(mish, conv3x3, instance), zero), Cell(Lincar3/hardswishh convixl, layer), id, Lhnear3hhardswish, dconv3x3, batch), Lhaear(hhaddswish, deonv3x3, batch), id, id), Cell(Linear3rrelu, conv3x3, instance). zero, id, zero, Linear3(mish, conv3x3, layer), avg. vyg.pool)), Residual2(Cell(cero,,, id, zero, (mish conv3x3, layer), avg- avg-pool, Linsar3mmshh, conv3x3, layer)), down, down), Residual2(Cell(2eoo, id, zero, Lmish, conv3x3, batch), avg avg-pool, Linsar3(mish, conv3x3, layer)), down, down)))
ImageNet-16-120) (mean test error 52.78 %, #params 0.626 MB, FLOPs 23.771 M):
avg-pool, id, id. Linear3(relu, deonv3x3, layer). zero), Cell(Linear(hhardswishh convixl, batch), zero. zero, Linh, deonv3x3, layer), zero, zero), CeIl(Lincar33reeu, dconv3x3, layer), Linear3(mish, dconv3x3, layer), zero, Lincar3(hardswish, conv3x3, layer), Lincar3(relu, dconv3x3, instance), Lin- car3(harsswish, conv3x3, instance))), Linear2(Cell(zero, Lincar3(relu, conv3x3, layer), (iish, cx1v batch), Linear3(mish, convixl, batch), avg.pool, Linear3(relu, conv3x3, layer)). Cell(id, id, (mish, conv3x3, layer). Linear3(relu, conv3x3, in- stance). id, id)), Residual2(Cell((zroo,, avg-pool, (mis,, conv 1x1, batch), Lin- car3(mish, conv lx1, layer), zero, zero), Cell(id, Lincar3(relu, dconv3x3, layer), zero, zero, Lincar3(relu, dconv3x3, instance), zero), Cell(id, Liccar3(relu, conv3x3, layer), id, zero, zero, id)) Cell(zero, (barsrhh conv3x3, layer), avg-pool, zero, Lin- car3(harswwssh, convixl, layer), id)), SesidaalBBeesiiaalllClliLieeeeee instance), Linear3mmish, conv layer), (iis, sonvix1, instance), zero, Lin- car3hhadswishh, dconv3x3, layer), id), Cell(id, avg pool, avg pool, Linear3(relu, convix1, instance). id, zero). Cell(avg pool, Linear3(mish. conv3x3, instance). Linsar3(mish, convixl, instance). Linear3(relu,, dconv3x3, batch), id, (harssshhardswish, conv3x3, instance))). Linear2 Linear3(relu, conv3x3, layer), Linear3(mish, conv batch), Lincar3(mish, convixl, batch), avg-pool, Lincar3(relu, conv3x3, instance)), Cell(id, zero, Lincar3(mish, conv3x3, layer), Lincar3(relu, conv3x3, instance), id, id)), Residuaa22CCClCLLiineEiiiiiii conv3x3, layer), Lincar3(mish, convixl, batch), id, Linca 1xl, layer), zero, id), down, down), Residual2(CallCLiinaarsce conv3x3, layer), zero, (rela, dconv3x3, layer), miih,, conv Ixl, layer), zero, id), down, down)). Linsar3(mish, convixl, layer), Linear3(mish, convixl, instance), avg grol, Lin- chrr(harsswihh, dconv3x3, layer), id), Cell(id. avg pool, avg. vool, Linear3(relu, convixl, instance), id, zero), Cell(avg-pool. Linsa conv3x3, instance), Lmish, conv Ixl, instance), Linear3(relu, dconv3x3, batch), id. (hadswih,, conv3x3, instance))), (Celer2(,,ll(zero,, Linear3(relu, conv3x3, layer), Linshr3mishh, convix1, batch), (mihh, convixl, batch), avg pool, Linear3(relu, conv3x3, layer)), Cell(id,
convixl,
conv lx1, instance).
35

---

Under review as a conference paper at ICLR 2023
zero, (mih,, conv3x3, layer). Lrelar3(relu, conv3x3, instance), id, id)) Resid- wal2(Cell(Linear3fruu) conv3x3, layer), avg-pool, id, Lincar3(mish, conv3x3, instance), zero, id), down, down), Residual2(Cell(Lineeettttth conv3x3, layer), zero, Lincar3(relu, dconv3x3, instance), Lincar3(mish, conv layer), zero, id), down, down)))
CIFARTile (mean test error 30.33 %, #params 2.356 MB, FLOPs 372.114
conv3x3, instance), id, zero, (rela, 3conv3x3, instance), (iis,r3 conv1x1, instance), avg pool), Cell(avg pool, avg pool. id, zero, Linear3(hardswish. conv3x3, batch), avg pool). (elle,, dconv3x3, instance). zero, id. Linear3(relu, dconv3x3, layer), id. id)). Residual2(Cell(zen, zero, Liis, convixi, instance). Linear3(mish, conv3x3, batch), zero, id), Cell(L.nnear((iss) conv3x3, instance), zero, Linear3(relu, dconv3x3, batch), id, Lincar3(mish, conv3x3, batch), id), CehlCiinear33hhrrswishh d batch), Linear3 conv3x3, batch), Linear3(relu, convixl, batch), zero, Linear3(relu, conv3x3, batch), id)), Siinea2(CCll(Limear3ee
dconv3x3, layer), Linear3(mish, conv Ix1, layer), id, zero, (mish, conv3x3, batch), (relar3(relu, dconv3x3, layer)). down), Lin- ear2(Cell(id, (harsrshhardswishhh convixl. layer), id, Linear3(relu, convixl, instance), avg-pool, avg wyg-pool, Linear3(relu, 1x1, layer)), down)), Linsar3(mish, conv 1xl, layer), Lin- avg avg-pool, (harssshh dconv3x3, instance), car3(hadsswish, dconv3x3, instance)), Cell(id, id, (reear3(relu, dconv3x3, layer), id, id, zero), Cell(L.inear3(relu, conv3x3, layer), id, avg-pool, (mish dconv3x3, in- stance), Linear3(relu,, convix1, layer), zero)), batch), Linsar3(mish, conv3x3, instance), zero, avg pool, avg pool, Linsar3(mish, conv convix1, batch)), Cell(Linear3(mishh, convixl, batch). Linear3(relu, dconv3x3, layer), zero, id, avg avg-pool, avg-pool), Cell(avg-pool) Linear3(hards wish, conv 1x1, instance), id, avg avg-pool, avg-pool, Lineac3haadssishh conv Ix1, instance))), Residual2(Cell(LLinee3eC dconv3x3, batch), avg-pool, id, avg-pool, id, zero), down, down), Resiidull((Cell(zroo, zero, Linear3(relu, dconv3x3, batch), avg-pool, Lhacar3(hardswish, conv Ixl, instance), avg pool), down, down)), chrrshhsss,shh, conv3x3, batch), (relar3(relu, convixl, instance), id, Linear3(relu, convixl, layer), Lielar3(relu, conv3x3, layer)). Cell(id. Linear3(relu, conv3x3, in- stance). Lhadwshhh convixl, instance), Linear3(relu, conv3x3, layer), avg avg-pool, Liish conv 1xl, layer)), Cell(zero, zero, id, Linear3(relu, conv3x3, batch), CelaBsCCCllLLinaaaaaaaavvve
3mist conv3x3,
conv3x3, batch), Lin-
id, Linear3(relu, conv 1x1, layer))). (harssih,,,,,sssh, conv3x3, batch), Lieear3 convix1, instance), Linear3(relu, deonv3x3, layer), Lincar3(mish, conv1x1, layer), Linear3(relu, conv3x3, batch)), Cell(id, Linear3(relu, conv3x3, instance), Linear3(hardswish, convix1, instance), I. (rela, doonv3x3, instance), avg pool, Lincar3(mish, convixl, layer)), Cell(zero, zero, id, Lin- car3(relu, conv3x3, batch), id, avg pool)). LCnear3(Cell(íd, id, avg pool, (mish, conv layer), Lmish, conv3x3, batch), zero). Cell(id, Linear3(relu, conv Ix1, batch), avg-pool, (rela conv 1x1, layer), avg-pool, zero), Cell(zero, Lrelar3 convixl, batch), Lincar3(mish, dconv3x3, batch), Lincar3(mish, convixl, batch), id, id)), Cell(id, Lhacar3hhardswish, conv 1x1, layer), zero, id, zero, id)), Linear3(Linnear zero, Lmish,3(mish, dconv3x3, instance). (mish, conv3x3, batch), Liis, dconv3x3, instance), Lrelar3(relu, conv 1x1, instance)), Cell(Linear3(relu, dconv3x3, in- stance), avg_pool, Linshr conv 1x1, instance), Lhardsshh,,,,wishh dconv3x3, in- stance), id, Lhanarrhhardswishh, lxnv layer))). Linear2(Cell(zeroo, zero, (iis, dcomv3x3, instance), (inlar3(relu,, conv3x3, instance), Lhnear3hhardswishh conv3x3, batch), avg pool). Cell(id, id, Linearhh conv instance), avg pool, zero, Lin- chardsasss,,hh, conv3x3, batch))), Cell(avg-pod (mish, dconv3x3, layer). zero avg avg-pool, avg-pool, zero)))
conv3x3, batch),
AddNIST (mean test error 6.33 %, #params 2.853 MB, FLOPPs 593.856 M):
Linearhhhrrdswish, dconv3x3, batch), (recar3(relu, convixl, layer), Lincar3(mish, conv3x3, batch), avg avg-pool, zero), Cell(zero, zero, avg pvol, id, avg. avg.pool, LinearXhhadssiish, convixl, instance)). Cell(Linear3rrelu, conv3x3, layer), id, zero, Liihh, conv3x3, instance), id, avg-pool)). LCelar2(Cell(id, Linear3(relu, conv3x3, layer), Linear3(relu, conv3x3, layer). (harssshh conv3x3, batch), id, Linear3(relu, conv3x3, layer)), Cell(Linear3(mishh, conv3x3, instance), id, Lin- car3(mish, conv3x3, batch), id, avg-pool, id)), Linear3(Cell((ero, id, Linear3(relu, dconv3x3. instance), Linear3(relu, dconv3x3. layer). Linear3(relu, dconv3x3, instance). Linsar3(mish, conv3x3. batch)), Cell(L.near3(mishh convixl, instance), zero, Lin- ear3(relu, conv3x3, instance), id, zero, Linear3(relu,, conv3x3, batch)), down), Lin-
36

---

Under review as a conference paper at ICLR 2023
ear3(Cell(eero, avg-pool. Linear3hhardswish, deonv3x3, layer). (reear3(relu, conv3x3, layer), Linear3hhardswish, convixl, instance), Lincar3hhardswish, conv3x3, batch)), Cell(LinearS(harrssish,, conv3x3, batch), Lincar3hhardswish, convlxl, layer), Lin- car3 conv 1x1, batch), id, Linear3hhardswish, conv3x3, batch), zero), down)), (aaaaaannnnaaaaeCCCeneeaaaaaaaa
convlx1, layer), avg-pool, (harsshhhrdswishh dconv3x3, batch), Liis,r3(mish, dconv3x3, batch), id, (iis,r3(mish, conv3x3, layer),, Cell(zero, Linear3(relu, dconv3x3, layer), Lhanarr(hardswish, conv3x3, instance), avg pool, avg pool, zero)). (imearr(CellLLinenr((eell) conv3x3, layer). Linsar3(mish. convixl. instance), id. Linear3(relu, dconv3x3, batch)), (mis,,, conv3x3, batch), Linear3(mish, convixl, instance). Lmish, conv3x3, instance), zero, Liisar3(mish, doonv3x3, layer), Linear3(relu, conv3x3, batch)), Cell(avg pool, Lincar3(mish, convixl, instance), (rela, conv3x3, batch), avg pool, id, Linsar3(mish, dconv3x3, batch))), Linear3(Cell(zero, avg wog. Lin- car3hhadswish,, dconv3x3, layer), Linear3(relu, conv3x3, batch). Linear3 conv 1x1, batch), (handsshharssisshh conv3x3, batch)), Cell(avg-pool. (harsss dxonv3x3, layer), LinearMmmish, convixl, batch), id, Lhaear,( conv3x3, batch), zero), down), Residnal2(Celllezro, (misar3(mish, convixl, instance), Lin- car chardhasss,,,h, convixl, instance), avg-pool, Linear3(relu, convix1, layer), Lin- chr3dhadswishh, dconv3x3, batch)), down, down)), (inearr(Lineaa2(CClliiinnaaa conv3x3, instance), id, Linear3(relu,, conv3x3, batch), avg-pool, zero, id), Cell(avg-pon Linear3 conv3x3, layer), avg.pool, Linear3mmshh, conv3x3, batch), Lin- car3(relu, conv3x3, batch), id)), Linear2(Cell(Iineaarrf 3 dconv3x3, batch), Linsar3(mish, dconv3x3, batch). id. (mish conv3x3, layer)). Cell(zero, Linear3(relu, deonv3x3, layer). (hardsshh.d conv3x3, instance). avg-pool, avg-pool, zero)). Linear2(Cell(id, Lieear3(relu, conv3x3, instance). Linear3 conv3x3, layer), Linnarhhhardswish, dconv3x3, batch), id, Lincar3(relu, conv3x3, layer)), (oll(L,ncar3mmish, conv batch), id, avg-pool, id, avg-pool, id)), Cell(id, Lincar3(rclu, conv3x3, layer), Linear3(mish, colvix1, instance), Lin- war3 conv3x3, batch), Linear3(mish, dconv3x3, instance), Lhansshhard Ixl, instance))). (eeaaaa(LLiieeeeCCCCeieaaaeCeee
conv3x3, batch), id, (reear3
conv layer), avg pool,
conv3x3, instance), id, Lin- car3(relu, conv3x3, batch), avg pool, zero, id), Cell(zero, Linear3(relu, conv 3x3, batch), avg avg-pool, Linear3(mish, conv3x3, batch), Linear3(relu, dconv3x3, instance), id)), Lin- (an3CCellLLineearrrel,, conv3x3, batch), id, Linear3(relu, conv3x3, layer), Linsa convlxl, layer), id. Linear3(relu, dconv3x3, instance)), CellL,nearr(mishh conv3x3, hatch), Linsar3(mish, convixl, instance), Lhnear3(hardswish, deonv3x3, instance), zero, (mish, dconv3x3, layer), Lincar3(relu,, conv3x3, hatch)), Cell(avg_pool, Lin- ear3(mish, cx,v1x1, instance), I. Linear3(relu, conv3x3, batch), avg pool, id, Linsar3(mish, doonv3x3, batch))), Linear2(Cellíid, Linear3(relu, conv3x3, layer). Thaear3hhardswish, conv3x3, layer). (harswshh dconv3x3, batch). id, Linear3(relu, conv3x3, layer)). C conv3x3, batch). id, avg avg-pool, id, avg-pool, id)). Cell(id, Lrnear3(relu, conv3x3, layer). Linsar3(mish, conv Ixl, instance). (harsshhhrddswihh. conv3x3, batch), Lincar3(mish, 3conv3x3, instance), 3inear3(mish, conv3x3, instance))))
The above reported architectures already yield strong performance. In particular, on ImageNet- 16- 120, CIFARTile, and AddNIST we find superior architectures with comparable number of pa- rameters and FLOPs to architectures from common cell- search spaces. When running the search for 50 additional evaluations, we further improved performance to test error of 51.98 % on ImageNet- 16- 12-12,, which is superior to the optimal architecture in the cell-based NAS-Bench- search space by 0.71 %p. We also found an architecture on CIFAR-100 when only allowing for the same primitive computations as in the cell-based NAS- search space, that achieves test error of 26.24 % and, thus, is also superior to the optimal architecture in the cell-based NAS- Bench- 201 search space by 0.25 %p. The found architectures from our huge hierarchical search spaces show that the search over a larger variety of architectures can indeed improve performance with a small search budget, even though the search problem is significantly more difficult.
37

---

Under review as a conference paper at ICLR 2023
40
CIFAR- 10.
38

---

Under review as a conference paper at ICLR 2023
C2
10
10
10
(b) CIFAR-100.
39

---

Under review as a conference paper at ICLR 2023
0C-30 NORE
40
40
(c) ImageNet16 120.
40

---

Under review as a conference paper at ICLR 2023
100
60
40
411
41
(d) CIFARTile.
41

---

Under review as a conference paper at ICLR 2023
10-4 CIP T PD
20.
1019
dor
12
20
(e) AddIIST.
Figure 15: Visualization of the best found architectures in our hierarchical NAS-Bench-201 search space. Abbreviations are defined as follows: ap=avg-pool. ba=batch, cl=convixl, c3=comv3xx cls=classifier, dc=3conv3x3, ha=hardswish, in=instance, la=layer, mismish, re=relu, and stm=stem. Best viewed with zoom.
42

---

Under review as a conference paper at ICLR 2023
Table 6: Definition of the binary and unary operations in the activation function search space Jact. The symbol B indicates per-channel trainable parameter and a (.) is the sigmoid function.
ads
21 +
pgouppian.oo Ieje www.innnnaii
expl SXp(-P(F) Io maal 2l a2
2UELE SQUUREW LooL
205
000
un3x ursdei
maxt F.
mull: Bub
P1 -22
Viz
wish
sinth
minte: 1)
varig id neg abs equaze
Ang +1 83mg
moonst
3
oosh
cosbis)
edgmoid
o(r)
Giv
aconst
+-3
tanh
tanla
l6gexp
log(1 (xp(a))
20g
loglle+
asinh
gaussian
expi-22)
bnin
[8]
eXP 2in
(ap())
atanh
tant. (2)
GEE
ecf(a)
a0igroic
(f2))
sin(s)
513c
sincls)
const
J SEARCHING FOR ACTIVATION FUNCTIONS
J.1 SEARCH SPACE
To search for activation functions, adopted the search space from Ramachandran et al. (007 More specifically, we define the following CFG Gaet
L2 : (LL,, L1, BINOP) UnIopo(LI)
L1 = (UNOP, UNOP, BINOP) UnTopo
BINOP add multi sub div bmax bmin bs gmoid bgauss an sq
beaussian wavg UNOP = id neg abs square cubic |
square.root moonst aconst
log exp sin cos
sinh |
cosh
tanh asinh atanh
| sinc
umax umin
| si sigmoid 1ogexp gaussian err const
(24)
where the binary operations (BINOP) and unary operations (UNOP) are specified in Table and BinTopo and UnTopo define the topology of binary or unary operations, respectively. The search space L(Gact) comprises ca. 10 potential activation functions. Note that the search space size can be varied by adding more levels or by using recursive formulation, i.e., ::= BinOp(L,II) UnOp(L) iid.
J.2 TRAINING DETAILS
Similar to Ramachandran et al. 2017)) we trained a ResNet-20 (He et al. 2016 on CIFAR-IC trained the network with SGD with learning rate of 0.1,
(Krizhevsky al. 2009). Specifically, momentum of 0.9, and weight decay of 0.0001, with a batch size 128 for 64K steps. The learning rate is divided by 10 after 32K and 48K steps. We used random flip with probability 0.5 followed by a random crop (32x32 with 4 pixel padding) and normalization. We split the training data into 45K training or 5K validation samples, respectively, and report final test error on the unseen test set (10K samples).
J.3 EXTENDED SEARCH RESULTS
Search costs The search cost was ca. GPU days using eight asynchronous workers, each with an NVIDIA RTX 2080 Ti GPU, for ca. 40 GPU days in total.
Best found activation function Our best found activation function for ResNet-20 is as follows: 3(a(=2:) min(ar, 0)) + (1
0), erf x:))
(25)
Figure 16 visualizes and compares the found activation function with common activation functions from the literature.
K BEST PRACTICES CHECKLIST FOR NAS RESEARCH
NAS research has faced challenges with reproducibility and fair empirical comparisons for a long time (Li Talwalkar 2020 Yang al. 2020a). In order promote fair and reproducible NAS
Table provides the license of CIFAR-10.
43

---

Under review as a conference paper at ICLR 2023
Bost found activation function
Common activation functions
ReLU
1.5
Sigmoid
1.0
GELU
3 0.5
0.5
Swish
0.0
Visualization of our best found activation function (see Equation 25 for different values Figure 16:
of the trainable parameter (left) and common activation function from the literature (right).
research, Lindauer Hutter (2020) created a best practices checklist for NAS research. Below, we address all points on the checklist.
1. Best Practices for Releasing Code
(a) Did you release code for the training pipeline used to evaluate the final architec- tures?, Did you release code for the search space?, Did you release code for your NAS method? [Yes] All code can be found at httptttt// http:/:s////nonmoouu..... 4open. sci
(b) Did you release the hyperparameters used for the final evaluation pipeline, as well as random seeds? [Yes] We provide experimental details (including hyperparameters as well as random seeds) in Section 5 Appendix [.] a.d
(c) Did you release hyperparameteess for your NAS method, as well as random seeds? [Yes] We discuss implementation details (including hyperparameters as well as ran- dom seeds) of our NAS method in Section 5 and Appendix
2. Best practices for comparing NAS methods
(a) For all NAS methods you compare, did you use exactly the same NAS benchmark, including the same dataset (with the same training-test split), search space and code for training the architectures and hyperparameters for that code? [Yes] We always used the same training pipelines during search and final evaluation.
(b) Did you control for confounding fuctors (different hardware, versions of deep learn- ing libraries, different runtimes for the different methods)? [Yes] We kept hardware, software versions, and runtimes fixed across our experiments to reduce effects con- founding factors.
(c) Did you ablation studies? [Yes] We compared different kernels (hWL, WL. NAS- BOT, and GCN) and investigated the surrogate performance Section We also an- alyzed the distribution of architectures during search, frequency of production rules, impact of the flexible parameterization of the convolutional blocks, test error vs. num- ber of parameters and FLOPs Appendix 1.2
(d) Did you use the same evaluation protocol for the methods being compared? [Yes]
(e) Did you compare performance over time? [Yes] We plotted results over the number of iterations, as typically done for black-box optimizers, and report the total search cost in Appendix [.2 For the activation function search, we not compare performance over time.
(f) Did you compare to random search? [Yes]
(g) Did you perform multiple runs of your experiments and report seeds? [Yes] We ran all search runs on the hierarchical or cell-based NAS-Bench Be-Bnchh--21 over three seeds, the search run for activation function for one seed, and surrogate regression experi- ments over 20 seeds.
(h) Did you use tabular or surrogate benchmarks for in-depth evaluations? [N/A] At the time of this work, there existed no surrogate benchmark for hierarchical NAS.
44

---

Under review as a conference paper at ICLR 2023
3. Best practices for reporting important details
(a) Did you report how you tuned hyperparameters, and what time and resources this required? [N/A] We have not tuned any hyperparameter.
(b) Did you report the time for the entire end-to-end NAS method (rather than, e.g., only for the search phase? [Yes] We report search times in Appendix [.2 and D.3 For the hierarchical NAS-Bent AAS-Benchh-201 experiments, the training protocols are exactly the same for the search and final evaluation (except for CIFAR-10), there are no additional costs for final evaluation. For the activation function search experiment, we used the same training protocol for training and evaluation.
(c) Did you report all the details of your experimental setup? [Yes] We report all experi- mental details in Section Appendix I.1 and J.2
45


Reviews:
[{"review_id": "v6lNQCF-F_", "reviewer": "Reviewer_Hxvj", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to represent neural architectures as algebraic terms and the design space (i.e. neural architecture search space) as context-free grammars (CFGs).  The authors then develop a Bayesian optimization algorithm building on top of the work by Ru et al., 2021 called BANAT, that exploits the CFG representation to define a hierarchical kernel. Results show BANAT benefits from the hierarchical kernel and outperforms common NAS baselines like random search and evolutionary search on NASBench-201 style search spaces.", "summary_of_the_review": "The authors present a simple, flexible formulation of neural architectures as algebraic terms and search spaces as CFGs. Along with this flexible search specification, the authors introduce BANAT, a BO-based NAS search method, that uses a hierarchical representation of architectures to learn and transfer across different granularities of representation in architecture space.  Although results look promising on a suite of experiments based on the NASBench201 benchmark, they do not\nsufficiently validate NASBAT relative to other baselines, nor do they provide enough coverage of different search spaces, in particular those that reach SOTA on CIFAR-10/ImageNet.  ", "strength_and_weaknesses": "Pros:\n- The CFG formulation of NAS search spaces is natural and flexible. \n\nCons:\n- The experiments are only conducted on NASBench201 style search spaces, which are small and do not achieve SOTA accuracy.\n- BANAT is only evaluated against simple baselines like random search and evolutionary search and not more adaptive competitors, in particular, other Bayesian NAS methods like HNAS (Ru et al., 2021), BANANAS, NASBOT, etc.\n- No evidence that the additional expressivity of the search space offered by BANAT results in interesting novel architectures. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pD89pYVP_UX", "reviewer": "Reviewer_hw2q", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a novel symbolic search space for NAS that allows generating architectures without predefined connection patterns.\n\nThe search space is derived from contextual-free gramma where the networks are presented as algebraic terms formed from neural operators.\n\nTo navigate through this search space, the author leverages Bayesian Optimization with a hierarchical WL kernel.\n\nExperiments are conducted on NAS-Bench-201, where the author shows that architectures derived from this search space surpass those generated by prior cell-based search spaces.", "summary_of_the_review": "The search space that this paper presents is valuable to the NAS community, and I vote for acceptance.", "strength_and_weaknesses": "Strength:\n\n- The presented search space is novel and different from existing architectural spaces. By itself, it counts as a solid contribution to the community.\n- The authors demonstrated the effectiveness of this search space over hand-engineered cell-based ones, leveraging the BO-hWL algorithm.\n\nWeakness:\n\n- [Minor] The search space itself still relies on existing patterns designed by human priors, e.g. the Cell(OP, OP, OP) operators, residual, and convolutions. Moreover, considering the sheer size of the search space, the search cost could be prohibitive beyond small-scale experiments. However, I don’t think it diminishes the contributions of this work. These issues could be left for future works to explore.\n- [Minor] Related work: The authors did a throughout survey of relevant NAS works in Section 5. Though it might also be worthwhile to also mention the topics of program synthesis or Neural-Symbolic Programming. The NSP community also has several existing works on adopting contextual-free grammar for discovering programs [1, 2]. Some also mentioned NAS since architectures can be viewed as a subset of differentiable programs [1, 2]. This work also inspires some recent AutoML methods, such as [3] where an algebraic search space is also proposed, but for a different task.\n\n[1] Shah et al, Learning Differentiable Programs with Admissible Neural Heuristics. NeurIPS 2020\n[2] Cui and Zhu, Differentiable Synthesis of Program Architectures. NeurIPS 2021\n[3] Wang et al. Efficient Non-Parametric Optimizer Search for Diverse Tasks. NeurIPS 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LOW0um6BoM", "reviewer": "Reviewer_P6Pi", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to use context free grammars (CFGs) to represent hierarchical search spaces for neural architecture search, towards the goal of discovering new architectures, rather than refining existing ones (an example of designing Transformers over CNNs is given in the introduction).\nArchitectures are represented using algebraic terms, and search are then defined by the means of related sets of production rules, terminals and nonterminals, constituting a CFG.\nFurther, a Bayesian optimization (BO) algorithm, utilizing hierarchical Weisfeiler-Lehman kernel (hWL), is proposed to efficiently search within large search spaces, produced with CFGs.\nExperiments are conducted on the NAS-Bench-201 (NB201) search space and its hierarchical variant, using CIFAR-10, CIFAR-100, ImageNet-16-120, CIFARTile and AddNIST datasets.", "summary_of_the_review": "While I like the motivation presented in the paper and the idea of using formal grammars seems somewhat compelling to me, in my opinion the paper currently does not contain convincing argumentation for using CFGs, neither does it provide sufficiently strong/interesting experimental results to consider it for publication.\n", "strength_and_weaknesses": "\n**Strengths:**\n\n - representing neural networks and related search spaces through formal grammars is an interesting research direction with a potential to deliver a convenient tool to work with complex hierarchical search spaces\n - the paper does a good job at explaining the idea and how different search spaces can be represented using this new approach (although this is presented mainly in the Appendix)\n - limitations of the work seem adequately mentioned (although I would still have some questions, see below)\n \n**Weaknesses:**\n\n - the paper does not clearly present what the benefits of adopting the proposed approach exactly are -- specifically, there are two main questions that are not sufficiently answered: 1) are there any qualitative gains from adopting grammar-based approach over traditional ways of representing search spaces (e.g., just writing PyTorch code specific to what we want to search)? By qualitative gains I mean that something becomes possible, which otherwise would not be; 2) what are the quantitative gains? That is, is it faster/easier/more flexible to use these grammars compared to using custom PyTorch code? Some important related questions:\n    - in Appendix E we can see how DARTS search space can be achieved - however, a common problem with DARTS is that even though when a supernet is created each consecutive node takes all previous outputs as its input (as in Figure 6), when deriving a final architecture we only keep two inputs, meaning that some of these connections have to be removed. Is it possible to efficiently represent this kind of constraints using CFGs?\n    - Is it possible to easily obtain supernets from a search space description (if it makes sense for the search space)?\n    - It seems that every time a searchable graph-based structure is included in a search space (NB201 cell, DARTS cell, etc.), it is represented a custom, purpose-built terminal - does it mean that CFGs are, broadly speaking, not the best choice when searching for arbitrary connectivity between operations? Or could these structures be expressed with additional production rules and simpler terminals?\n - Related to the above, but focused more on the high-level direction of this research: considering that we have to define all terminals, nonterminals and production rules (which I imagine would involve providing implementation for each element), is the overall effort and process of designing a search space fundamentally different when using CFGs compared to just doing hierarchical NAS? Specifically, I do not see how using CFGs brings us closer to the goal of automatically discovering novel architectures (like Transfomers) - in the end it seems we are still primarily limited by the primitives (operations, architectural patterns, etc.) that we decide to include in our search space, just like it is the case for the most (all?) of the existing methods.\n - evaluation of the proposed method is rather limited - I felt a bit disappointed by its scope and the choice of baselines, specifically:\n    - only one, very simple search space is considered; although the fact that NB201 search space is extended does help, still the evaluation does not really match what can be usually found in NAS papers\n    - selected baselines are all very simple methods - there are many very efficient NAS methods out there, e.g., the entire research field of zero-cost NAS (\"Zero-Cost Proxies for Lightweight NAS\", \"Neural Architecture Search without Training\", \"Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective\", to name just a few papers) seems like a good fit to \"search efficiently in the huge search spaces spanned by our algebraic architecture terms\", but the authors only include random, evolutionary and BO search, which are one of the most basic approaches\n    - similarly, applicability of some efficient one-shot NAS methods, which constitute an important subfield in NAS, is not explored at all (related to one of my questions above)\n    \n**Minor shortcoming and suggestions:**\n\n - consider changing \"Linear\" to, for example, \"Sequential\" - the word \"linear\" is commonly associated with linear operations, not with a chain of sequential operations\n - \"However, there is of course no single search space that can construct any neural architecture\" I assume the authors meant that it is impossible to define a single search space _using CFGs_, that would include any neural architecture? I would argue that an implicitly defined search space obtained by considering basic graph operations (such as add a node, add an edge, assign operation, etc.) together with a starting graph (e.g., empty graph) would include any neural network realizable in practice. How big such a search space would be, or if it would be easy to use some searching algorithms within it is a different question - although please note that there exist NAS papers that defined search spaces in such way.\n - Equations 4 and 8 are somewhat redundant, Equation 8 does not seem to add much on top of Equation 4, just minor details - in general, in my opinion, Sections 2 and 3 could be combined and made shorter, and the saved space could be used to include some of the things I mentioned are currently missing from the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HAK2jCJiyRP", "reviewer": "Reviewer_Y2hs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a CFG-based approach for specifying architecture search spaces. They demonstrate the expressivity of their approach, propose a BO-based schemes for searching it while handling the massive hierarchical search space, and evaluate by searching for architectures on several vision datasets.", "summary_of_the_review": "I believe the work to be an interesting approach to discovering neural architectures from scratch, and there are some interesting experimental results, so I would be in favor of the paper appearing at the conference. The fairly limited nature of the empirical evaluation, missing discussion of recent work on from-scratch AutoML, and opaque presentation of the method prevent me from giving a stronger endorsement.", "strength_and_weaknesses": "### Strengths:\n1. The CFG-based approach for specifying large search spaces seems fairly novel and interesting, in-particular allowing for very large search spaces while dealing with issues of dimensionality and other constraints.\n2. The authors provide code and furthermore make an effort to ensure impact via both PyTorch and Tensorflow APIs.\n3. The presentation of the experimental section is very clear and directly lays out what questions are being answered. Empirically, the results show that the larger search space can be fruitfully searched for stronger architectures than are contained in the NB201 search space, at least on ImageNet-16-120 and the two recently introduced tasks.\n\n### Weaknesses:\n1. The “from Scratch” nature of the work may be somewhat overstated, as the user must still specify primitives such as convolutions being used. The authors motivate the work by noting the Transformer was not discovered by NAS, but is there any hope that a search space generated along these lines would encode its crucial attention mechanism while not being so vast as to be unsearchable? Notably, there has been recent work on “from Scratch” AutoML (Real et al., 2020) and NAS (Roberts et al., 2021) that do aim for such generality.\n2. It is not entirely clear that the CFG formalism is crucial for defining and constraining search spaces. It could be useful to compare to other AutoML search space definitions, e.g. the domain-specific language for optimizer search of Bello et al. (2017).\n3. The related work noted in the two points above is missing.\n4. The methods sections of the paper are difficult to follow without either familiarity with CFGs (not safe to assume for ICLR). There is a lot of relegation of detail to the appendix, both for the search space design and for the search methods.\n5. The experimental section could benefit from demonstrations with search spaces beyond NB201, and on tasks beyond computer vision, especially since as the authors note the algorithms for vision have already been highly optimized. Some important comparisons/ablations are missing, such as whether FLOPs are also comparable to NB201, and whether it is important to have multiple kinds of activation function in the search space, or if performance is the same if only the one used by NB201 is allowed?\n\n### Questions:\n- Is “any neural architecture can be represented algebraically” a formal claim? If yes where is the definition of a neural architecture and proof of the result? Does this fact hold e.g. for recurrent nets?\n- Equation 4: presumably f also includes some fixed training procedure for all networks?\n- Why is “our grammar-based mechanism does not (generally) support simple scalability of discovered neural architectures (e.g., repetition of building blocks)” true given the use of the CL to capture NB-201? \n\n### References:\n- Bello, Zoph, Vasudevan, Le. *Neural optimizer search with reinforcement learning*. ICML 2017.\n- Real, Liang, So, Le. *AutoML-Zero: Evolving machine learning algorithms from scratch*. ICML 2020.\n- Roberts, Khodak, Dao, Li, Re, Talwalkar. *Rethinking neural operations for diverse tasks*. NeurIPS 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5xqvlvU2Sm", "reviewer": "Reviewer_Xuih", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes using context free grammars to define a search space. This grammar is very flexible and one can use it to define all kinds of search spaces. The production rules can be formed to imposed constraints as well. Their search algorithm, BANAT is a bayesian optimization based one, where the surrogate model is a hierarchical Weisfeiler-Lehman kernel (adapted Weisfeiler-Lehman kernel used by NASBOWL to make it work for their search space) and the acquisition function is expected improvement. They used a hierarchical NASBENCH 201 search space. ", "summary_of_the_review": " The main novelty is the ability to define a context free grammar for a given search space. It is not evident if this is actually useful in practice. The surrogate model used by BANAT is a minor adaptation of NASBOWL paper which used Weisfeiler-Lehman for a regular NASBENCH search space to make it work for hierarchical setting. They also need to compare their algorithm against other hierarchical search space based algorithms.", "strength_and_weaknesses": "Strength:\n1. This paper defines a language for defining search spaces. Their grammar can be used for all the search spaces.\n2. Their search algorithm is able to find better architectures faster than others in hierarchical NAS-Bench 201 search space (as they are using a surrogate model).\n3. In their empirical evaluations, it was highlighted that while cell-based search space works well for cifar-10, cifar-100 and imagenet-16-120, it does not perform well on CIFARTile or AddNIST. \n\n** Comments / Questions **\nIt is a bit hard to understand why we need a special grammar to design the search space. The authors claim it is more flexible and can discover new architectures. But one still needs to design the primitives and how they are connected together. So how can we really discover completely new architectures?\n1. Hierarchical search space is much larger than cell spaced search space and is used for scenarios where one is interested in finding architectures with low latency, number of flops etc. So it is not surprising that BANAT was able to discover architectures with lesser number of parameters. It would have been better if they had actually demonstrated how it fared in multi-objective optimization problems and compared against other hierarchical baselines such as MNASNet. \n3. The authors claim that their search space design is more flexible than other baselines and is especially beneficial for object detection setting. But they never ran BANAT to find architectures for object detection.\n4. For figure4, Kendall Tau is the most commonly metric. Please use that.\n5. Please use a diagram to elucidate how the hierarchical search space looks like\n6. Please specify the details about bayesian optimization such as the acquisition function used in the main paper rather than in the appendix.\n7. The time taken for Imagenet-16-120 is 1.8 * 8 GPU days. Please specify that explicitly. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject