Runtime Analysis of Evolutionary NAS for Multiclass Classification
Authors: Zeqiong Lv
Chao Qian
Yun Liu
Jiahao Fan
Yanan Sun
Venue: ICML 2025 poster (2025)
Keywords: Evolutionary neural architecture search; evolutionary machine learning; evolutionary algorithm
Primary area: theory->deep_learning

Abstract: Evolutionary neural architecture search (ENAS) is a key part of evolutionary machine learning, which commonly utilizes evolutionary algorithms (EAs) to automatically design high-performing deep neural architectures. During past years, various ENAS methods have been proposed with exceptional performance. However, the theory research of ENAS is still in the infant. In this work, we step for the runtime analysis, which is an essential theory aspect of EAs, of ENAS upon multiclass classification problems. Specifically, we first propose a benchmark to lay the groundwork for the analysis. Furthermore, we design a two-level search space, making it suitable for multiclass classification problems and consistent with the common settings of ENAS. Based on both designs, we consider (1+1)-ENAS algorithms with one-bit and bit-wise mutations, and analyze their upper and lower bounds on the expected runtime. We prove that the algorithm using both mutations can find the optimum with the expected runtime upper bound of $O(rM\ln{rM})$ and lower bound of $\Omega(rM\ln{M})$. This suggests that a simple one-bit mutation may be greatly considered, given that most state-of-the-art ENAS methods are laboriously designed with the bit-wise mutation. Empirical studies also support our theoretical proof.

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Zeqiong Lv!
Chao Qian²
Yun Liu'
Jiahao Fan
Yanan Sun" x1
Abstract
2022; Liu et al., 2023; Miikkulainen et al., 2024) employs evolutionary techniques, primarily evolutionary algorithms (EAs), for the automation and has been widely used in real- world applications (Sun et al., 2019b; So et al., 2021; Liu et al., 2023; Yang et al., 2023; Yan et al., 2024). However, the theoretical research of ENAS is still underdeveloped.
Evolutionary neural architecture search (ENAS) is a key part of evolutionary machine learning, which commonly utilizes evolutionary algorithms (EAs) to automatically design pigh-performing deep neural architectures. During past years, var- ious ENAS methods have been proposed with exceptional performance. However, the theory research of ENAS still in the infant. In this work, we step for the runtime analysis, which is an essential theory aspect of EAs, of ENAS upon multiclass classification problems. Specifically, we first propose benchmark to lay the ground- work for the analysis. Furthermore, we design a two-level search space, making it suitable for mul- ticlass classification problems and consistent with the common settings of ENAS. Based on both de- signs, we consider (1+1)- I-NNSS algorithms with one-bit and bit-wise mutations, and analyze their upper and lower bounds on the expected runtime. We prove that the algorithm using both mutations can find the optimum with the expected runtime upper bound of Orr In rM) ) and lower bound of Mr In M). This suggests that a simple one- bit mutation may be greatly considered, given that most state-of-the ously designed with the bit-wise mutation. Em- pirical studies also support our theoretical proof.
Generally, the theoretical research of ENAS follows the con- ventional theory of EAs. One essential topic in this aspect is the runtime analysis (Auger & Doerr, 2011: Neumann & Witt, 2010; Zhou et al., 2019; Doerr & Neumann, 2020), which represents the expected number of fitness evaluations until an optimal or approximate solution is found for the first time. In practice, the runtime analysis is very chal- lenging, primarily due to the randomized nature of EAs. Therefore, the community typically begins with (1+1)-EA with various mutations upon benchmark problems which have mathematically formulated fitness functions. For ex- ample, theoreticians (Droste et al., 2002; Doerr et al., 2008; Doerr & Goldberg, 2013; Witr, 2013) have analyzed the runtime of (1+1)-EA with one-bit mutation or bit-wise mu- tation ONEMAX and LEADINGŌNES functions. These analyses further provide theoretical insights for configuring EAs to solve complex problems like the dynamic makespan scheduling problem, where (1+I)-EA with bit-wise mu- tation efficiently maintains a good discrepancy when the processing time of a job changes dynamically (Neumann Witt, 2015).
ENAS methods are labori-
In the context of runtime analysis, mathematically formu- lated fitness function plays the role of directly assessing the progress of the search process of EAs (Auger & Doerr, 2011; Neumann & Witt, 2010; Zhou et al., 2019; Doerr & Neumann, 2020). However, constructing such a math- ematically formulated fitness function for ENAS very challenging. This is because the fitness of neural architec- ture is obtained by training itself with learning algorithms, of which the whole process is difficult to be mathematically formulated since it is inherently black-box.
1. Introduction
Neural architecture search (NAS) can automate the design of effective deep neural architectures (Elsken al., 2019), making itself crucial step in automating machine learn- ing (He et al., 2021). Evolutionary NAS (ENAS) (Real et al., 2017; Liu et al., 2018; Real et al., 2019; Ünal & Başçiftęi,
'College of Computer Science. Sichuan University, China "Naiional Key Laboratory for Novel Software Technology, and School of Artificial Intelligence, Nanjing University, China. Cor- respondence to: Yanan Sun <ysun <<sum@ssuu.cuu.cn. scu.edu.cn..
In the literature, there is only rare work making attempts to mathematically formulate fitness functions for machine learning tasks. Fischer et al. (2023) considered the classi- fication of points the unit hypersphere and constructed fitness function that quantitatively reflects the proportion of correctly classified points. This is done by leveraging
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Three Types of Blocks
Call 1:
Input
Blocks
P
x I
Salect
Oall 2
Softrrx
P
from
(A-type block)
Blocks
(B-type block)
[C-type block))
Anp-e B-type, or C-type block that can output hinary set
Pa--1
A binary neuron with binary threshold activation function, which output orl AnAND newron that can compute the Boolean AD and output 0 er An OR neuron that can compate the Boolsan OR and output 0 or
Call M+
Blocks
OR
PM
Output Layer
A neuron No. with weight Wmm and bios Dyn 0 (except for by 0.1 when m M) that can oulpul. value Am to the Soltmax layer
Figure 1. The neural architecture skeleton, including a set of cells where each of them consists a set blocks. There are three types blocks: A-type, B-type, and C-type. Each block receives the input and outputs a binary bit (1 or 0). Thus, M - 1 cells will output a binary set for cach neuron {N1, ... Nax) Each neuron No computes value hn. which then normalized by the Softmax
layer to yield the probability Pm. The class label corresponding to the highest probability is chosen as the final classification result.
the hyperplane parameters representing a neural network, thus providing a way to evaluate the neural networks. Upon this, Fischer al. (2024) introduced a bending hyperplane and used its parameters to mathematically formulate a more advanced fitness function. However, the fitness functions in these works evaluate neural networks with fixed architec- ture, which is in contrast to ENAS, where the architectures are varied through evolution. To this end, Lv et al. (2024b) developed an intuitive fitness function for the evolved neu- ral architectures. This function incorporates polytope- based decision boundaries alongside hyperplanes and mathemati- cally quantifies the volume of the correct decision regions. However, this work only focused on binary classification problems. In practice, many real-world applications, such as image recognition, speech recognition, and medical diag- nosis, require distinguishing between multiple classes.
lem McC with M classes, based on which a fitness func- tion is mathematically formulated to evaluate the quality of any given neural architecture in solving this problem. The fitness function can serve as a benchmark for other theoretical aspects of ENAS, which then help hance the understanding of ENAS and provide insight for designing better ENAS algorithms.
2) We design a more practical search space with two inter- related levels. where the first level is cell-based and the second level is block-based. This search space with solu- tion length M is consistent with the common setting of ENAS and supports the theoretical analysis of ENAS for multiclass classification problems.
3) We analyze the expected runtime bounds of (1+1)-ENAS algorithms with one-bit and bit-wise mutations in search- ing for the optimal neural architecture of Mcc. The proven runtime bounds (Theorems 4.1 to 4.4) show that one-bit and bit-wise mutations achieve nearly the same performance for (1+1) (1+1)-ENAS. We also conduct empirical analysis to verify the theoretical proofs. To the best of our knowledge, this is the first theoretical work of ENAS for multiclass classification problems.
On the other hand, the representation of the search space in the current theoretical works also hinders the runtime analysis of ENAS for multiclass classification. So far, only one related work has been conducted (Lv et al., 2024b), but the search space considered has some limitations. Specif- ically, it is unable to handle multiclass classification prob- lems, since the design of the neural architecture's skeleton only enables distinguishing between two decision spaces corresponding to two classes. Moreover, the search space restricted the analysis of ENAS algorithms with common evolutionary strategies, such the bit-wise mutation op- erator, as it resulted in solution of length three. To start the runtime analysis of ENAS for multiclass classification problems, a more powerful and practical search space is urgently needed.
2. Preliminaries
This section presents the foundations of considered neu- ral architectures for multiclass classification, followed by introducing the ENAS algorithm.
2.1. Considered Neural Architectures
We consider neural architecture for multiclass classifica- tion. This architecture reduces the multiclass classification to multiple binary classifications (Friedman et al., 2000), each is solved by a binary classifier. The final classifica- tion result is then obtained by aggregating the weighted outcomes from these binary classifiers (Aly, 2005).
This work makes an initial attempt for the runtime analy- sis of the ENAS algorithm for multiclass classification problem. The main contributions are summarized below:
1) We propose a multiclass classification benchmark prob-
2

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
The skeleton of the neural architecture is shown in Figure 1. The input instance is fed into M 1 cells, each of which is treated binary classifier that outputs either 0 or 1. The outputs of these M - 1 cells are then fed into a hidden layer consisting of M neurons. The hidden layer is designed to collect the results from each of the M - 1 binary classifiers and integrate them to prepare for computing the probabilities of the input belonging to each class. We fix the biases and weights of the M neurons as follows: 1) except for the last neuron NM. whose bias is bm- 0.1, all other neurons have a bias of 0; 2) the weights satisfy
As detailed in Section 2.1, a neural architecture consists of M - 1 cells, each of which includes A-type, B-type, and C- type blocks. We let the number of these blocks in the m-th cell be n "B. and nc respectively. Then, we encode a neural architecture using M - 1 triplets of integers, where each triplet corresponds to the counts of each block type in a cell. The encoding of a neural architecture is given by:
x= ( n ml).................... (n M-1 M
. m -))
.B
Based on this encoding mechanism, the search space is S = {z x E x 23-- This is a two-level search space with cells at the first level and blocks at the second level. By following the convention in EA's runtime analysis. we consider the (1+1)-ENAS algorithm based on (1+1)-EA with mutation only, which serves theoretical foundation for runtime analysis and algorithm design. Its main steps are:
Vi: wa,s = 1, W = 0.5, W1,1-1 = 0.4, Vi 1, 13 wi, = 0.
Such settings make the output of Nas be maximized when the cells output 0M-1, thereby correctly classifying the M-th class. For any output h; E h2.,,...... hMr from the M neurons, the softmax activation function (Sharma et al., 2017) is applied to compute e/ Σm= e as the probability Pj of the input instance belonging to class i. Finally, the classification result is class arg.na;gg11.M)) P..
1. Randomly sample n (n E [L..M - 1],² e {A, CJ) in the initial solution according to the uniform distribution s[,, where E N+ is an gesorithm-speciff parameter.
The core of the considered neural architecture is cell, which serves as a fundamental building unit commonly used in the ENAS community (Elsken et al., 2019; Liu et al., 2023; Zoph et al., 2018; Real et al., 2019). Each cell consists of blocks and one OR neuron, allowing for flexible and intricate topological structures (Sun et al., 2019a; Zhong et al., 2018). Each block will output binary bit. Then, the OR neuron in the cell will receive bits from the / blocks and output either 0 or 1.
Generate offspring by executing mutation on a parent.
3. Select the solution with higher fitness to enter into the next iteration. In case of ties, the offspring is preferred to the parent by the selection operator.
4. Repeat Steps 2 and 3 until an optimal solution is found.
In the above steps, mutation plays a key role in guiding the search process, with two commonly used types in the ENAS community: the one-bit mutation that changes only one po- sition, and the bit-wise mutation that changes each position with a certain probability. These two mutations typically affect the runtime of the algorithm, which will be separately examined in the 11+1)-ENAS algorithm. Specifically, we employ a "two-level" mutation process: an outer-level mu- tation that selects cells for mutation and an inner-level mu- tation that alters blocks within the selected cells. The outer- level mutation can be either one-bit mutation, which mutates one randomly selected cell, or bit-wise mutation, which mu- tates each cell independently with probability 1/(M 1). The inner-level mutation, executed after the outer-level mu- tation, can be either local (mutating each selected cell once) or global (mutating K times, with K ~ Pois(1)) (Kratsch et al., 2010; Durrett et al., 2011; Qian et al., 2015; 2023) mutation. For each time of mutation, the algorithm applies the operation defined in Definition 2.1.
Three types of block are sufficient to build a neural archi- tecture that can tackle most classification problems: A-type, B-rype, and C-type blocks, as suggested in (Lv et al., 2024b) and shown in the top-right of Figure Each block contains at least one binary neuron with binary step function (Sharma et al., 2017), and at most one AND neuron to compute the Boolean AND of the binary outputs from the previ- ous neurons. Based on this, these three types of blocks allow the neural architecture with 2-dimensional input to form decision regions (Gibson & Cowan, 2002; Nguyen et al., 2018) in the shape of segment, sector, and triangle, respectively. These decision regions are representatives of half-space- unbounded polyhedron, and bounded polyhe- dron, and most classification problems can be described as their disjoint union (Bertsimas& & Tsitsiklis, 1997). Further details about the considered neural architecture are provided in Appendix A.
Definition 2.1 (Mutation Operation). Given any cell (n" nC) of a solution, the algorithm randomly se- lects a block type V E {A, B, C} and applies one of the following operations uniformly at random: (1) Addi-
2.2. ENAS Algorithm
ENAS algorithms aim to search for an optimal or approxi- mate neural architecture from a search space consisting of all potential solutions (Elsken et al., 2019; Liu et al., 2023).
tion: adds a V-type block (i.e., ny + n + 1); (2) Dele-
tion: deletes a Vtypee block (i.e., n < n 1) when
3

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Regiee
Neural Architecture
eyp
Drgge
Impuit Instance
D-gge
Output Probabilittiss
1
(0. A5)
Cal
us
Saltra
[R. = P(y= 1 'T) = 0.25 Ps - PC - 22 - 0.45
[.. PG = 3) = 0.30
Drgge
M55 0.1
Digge
0.5
T1s Doo
Frad by A-gg
(a) MCC with M 3
(b) Decision Regions
(c) Classification Example
Figure 2. Illustration of neural architecture solving Mcc. (a) McC with M 3 and r = 2, depicting 3-class classification problem. The points labeled as class 1, 2, and 3 are colored off-white, yellow, and khaki, respectively. Each class (e.g., class 1) has two segments (e.g.. Sing Stnng. ). two sectors (c.g., S U Stcc), and two triangles (c.g.. S.. U S(n).. (b) Decision regions produced by neural architecture {(0, 3, 0), (1, 3, 0)}: blue arrows point to class I (excluding the red-arrow regions), red arrows point to class 2, and the remaining regions to class The regions marked with a "V" are correctly classified. (c) Classification example for input instance (0.5, 0.5) E Sece architeeciiiii
using neural architecture {(0,3, 3, 0), 3, 0)}. The first cell outputs 0 since it has no block to cover the region S while the second
cell outputs since it has a B-type block to cover the region Sa... The neurons (Ni, NN3 then output values of 0.4, 1.0, and 0.6. e respectively. The softmax layer converts these into prohabilities of 0.25, 0.45, 0.3, and class (0.45) is chosen as the classification result.
n > 0: (3) Modification: randomly selects a block type W E {A, B, CJAV and then performs Deletion on V while performs Addition on W when ny > 0 (i.e., nz -> nz and nW + nw + 1); otherwise, ni and nw remain un- changed.
These differences introduce three challenges: 1) problem definition: accurately modeling inter-class dependencies and region-specífic sample distributions: 2) fitness function: mathematically formulating the fitness (i.e., classification accuracy) of neural architectures from geometric properties; 3) search space partition: partitioning the search space by analyzing the interactions between architectural components (e.g., blocks, cells).
Notably, there is sequence in the two-level mutation pro- cess, i.e., first selecting the cell to mutate (outer-level muta- tion) and then applying the mutation (inner-level mutation) to the selected cell. Reversing the sequence would make the algoritheg infeasible, as the index of the cell to be mutated would be unknown, making unclear where the inner-level mutation should be applied. Specifically, given a solution ær which is encoded by M - 1 triplets of integers, i.e., = ((n'), n/3. n......, (m M-1 , M-1
sequecte
wouldmnn
To tackle the above challenges, this section defines a multi- class classification problem named McC and a fitness func- tion that evaluates the quality of neural architectures sol it. The search space of the problem is then partitioned to facilitate runtime analysis.
, .nc -) the al- gorithm must first select the cell index m E {1,.... M 1), 1}, and then apply the inner-level mutation to modify the se-
3.1. Problem Definition
We propose multiclass classification benchmark problem McC that captures essential properties of real-world multi- class classificatton diassifiication tasks, including both linearly and non- linearly divisible decision regions (e.g., half-space region, unbounded/boundder polyhedra region). As defined in Defi- nition 3.1, the input is a 2-dimensional input vector as sug- gested in the binary classification benchmark problems (Fis- cher al., 2023; Ly et al., 2024b); the output label (class) takes on one of M labels.
lected cell (n" ng..n. nz).
3. A Multiclass Classification Classification Problem
The differences of the classificationn problem and the bi- nary classification problem (Lv et al., 2024b) for ENAS algorithms include the following: 1) decision regions: mul- ticlass pesssificaii divides input space into M decision regions (vs. two in binary (lassificationn) Increasing neural classification),
region
architectural demands; in 2) classification accuracy: multiclass classification aggregates per-class accuracy across all M re- gions, amplifying the complexity of the fitness evaluation; 3) search space: the neural architecture for solving multiclass classification is a combination of multiple binary classifiers or a more complex architecture (vs. binary classification' 's binary classifier), exponentially expanding the search space.
Definition 3.1 (Mcc Problem). Let the inputs consist of the points the unit circle S == {ar E R² ||>||| < 1). with each point labeled as class y E [1..M]. where M 2 2. The unit circle S is evenly divided into n = 2r sectors with angle 2T where r 2 2. Thus, S = S sees with She representing the k-th sector. Each sector St. can be further divided into triangle St with area 1 sin( sin(2=)
combinatied
expone
2x) and
an
4

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
segment (a segment is cut from a sector by chord) Seeg with area Σ - sin )) Let the points with label m be distributed across segmenets, r sectors, and triangles, with the corresponding regions denoted as Seg"". "Se""", and Tri",, respectively. These regions are defined as follows:
where CmM is the set of points that are covered by the blocks in the m-th cell of the neural architecture, L represents the set of points with label m, Cm R and vol(.) denotes the area. U (C n (m) represents the set of points that are correctly classified in classes 1 to M 1, and (nm=) c n C.)) is the set of points that are cor- rectly classified in class M. For example, in the case of Figure 2(b), we have (n C. n h/24)) L \ as the second cell misclassifies Sgeg of class 3; the classifica- tion accuracy can be calculated according to Eq. (1), i... ((4 Arsec sec + + Artri + 1- Araeg) + (2- Arsec + 2 Artri +
2r
Sec Ü
5m++(k (
Tri Th
(k-+kk1)MM
trl
k=1
k=++1
2r
Segm#1
U
(1m-1)+(k- 1JM 'Seg'
U
SkM
San
k=r+1
k=++1
Then, the set of points with label vn E [1..M] is
1 Arseg) (//e)))// T ~ 0.83.
c = Seg" t U See U Tri".
In general, three kinds of regions need to be fit in each class: (1) a = r segment regions (A-type), (2) b = r sector re- gions (B-type, or A-type plus C-type), and (3) c r triangle regions (C-type). From the perspective of neural architec- ture optimization, there are six important block counts to consider in each cell of neural architecture:
An example of McC (M- = 3, r r- 2, n = 12) is shown in Figure 2(a). The problem has the following characteris- ties: (1) The decision region of a class is the disjoint union of r half-spaces (segments), r unbounded polyhedra (sec- tors), and r bounded polyhedra (triangles). (2) Triangles and sectors of the same class are never connected. For ex- ample, in Figure 2(a), triangle Sh of class is bordered by sector of class 2 and a triangle of class 3. (3) Segment Sang connected to triangle Sin of class m must belong to class (m + 1) mod M. For example, St. in Figure 2(a) belongs to class 1, whereas Slag belongs to class 2. In our work, we explore how fast does the ENAS algorithm can find an optimal neural architecture that correctly forms all of the decision regions in the McC problem.
1) n'A: Number of A-type blocks that classify segments.
2) n"; Number of A-type blocks that classify sectors (to- gether with C-block).
3) n'z: Number of B-type blocks that classify sectors alone.
4) n'c Number of C-type blocks that classify sectors (to- gether with an A-type block).
5) n² Number of C-type blocks that classify triangles.
We consider the neural architecture described in Section 2.1 to solve the McC problem. Figure 2(b) depicts the deci- sion regions of the neural architecture ((n)) = 0, n. = 3, mg. = 0), (n² = n = 3, no. = 0)}. which visually demonstrates how neural architecture solves the problem shown in Figure 2(a). The decision region for class ex- cludes Sty due to the use of an A-type block in the second cell, which leads to this region being classified as class 2. This highlights how the neural architecture addresses the complex inter-class relationship in multi-class classification. Based on the above, Figure 2(c) presents an example of how the neural architecture classifies specific input instance, with detailed computation from input output. Additional classification examples can be found in Appendix B.
6) n'g: Number of B-type blocks that correctly classify the triangles but incorrectly classify the segments.
For the (M - 1)-th cell, when ng < b, the missing b - RB B-type blocks need to be compensated by A-type and C- type blocks. In this case, we need n% 2 - nB (i.e.. nA 2 a and n'c 2 b-bnngg ng (i.e., nc 2 c+b-ng)) In addition, if nn b and nc C, then there must be n 0 segments in Seg" M that are misclassified as class M - 1, due to insufficient C-type blocks. To avoid this, we must ensure n2 0, i.e., we need no 2 n² 2 to ensure that all triangles of class M - are correctly classified by C-type blocks. Overall, the (M - 1) cell of the optimum needs to satisfy the following conditions:
The classification accuracy (H) of parameterized neu- ral architecture H can be defined as the ratio of correctly classified points by H to the total number of points in the unit circle S, which is intuitive, easy to understand, and suitable for balanced datasets because it does not consider the class distribution (Grandini et al., 2020). Thus, we have
n 2 a + (0, b =nn} max(r, 2r n1
ny + 2 b c 2r,
no c
These conditions must also be satisfied for the other cells; otherwise, some points will be misclassified as class M.
(H) = voll vol((U (c"" (aacc")))uunnn (u()))nn(MM)) M-! )"")
v5](5)
5

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
3.2. Mathematically Formulated Fitness Function
resulting in all cells outputting O-bits, which allows only the neuron NM with non-zero bias to output a value greater than 0 (specifically, 0.1). However, point in Seg may be misclassified by the (M - 1)-th cell. Specifically, if the value n" of the (M - 1)-th cell is greater than O, then m M- 6), (c - M }}} segments of class M will be incorrectly classified; otherwise, all segments of class M are correctly classified. Let cæ denote the number of misclassified segments of class M. Then, we have
ENAS primarily focuses on the evolution of neural architec- ture, leaving the fitness evaluation of architecture to learning algorithms (such the gradient-based algorithm) (Elsken et al., 2019). However, the practical optimization methods may not guarantee the achievement of the optimal parame- ters. To analyze ENAS purely, we assume that the optimal or approximate parameters of each evolved architecture can be achieved in fitness evaluation, as we discussed in Sec- tion 2.1. Based this assumption, we can mathematically formulate fitness function to describe how the basic units (i.e., cells and blocks) of neural architecture influence its fitness on the MCC problem.
M
c max min m (n b), (c no 1)) [0..r].
Consequently, b+ c 2r triangles and a+ 1 Cw = 2r co
segments of class M - 1 can be correctly classified.
Before formulating the fitness function, we define two key quantities related to the solution æ, which reflect the number of decision regions that the solution can form. One is the number of decision regions shaped as triangles that can be correctly formed by the m-th cell of æ, which is denoted as 1" and can be calculated by
By combining the two terms in the numerator of Eq. (1), we can derive the number of triangles and segments (including those within sectors) that can be correctly classified by x. Specifically, I, + 2r triangles and Jæ 2r C segments are correctly classified. Additionally, we have Ja + 2r [2r, n]. where the lower bound of 2r holds because Ex E [2r,
In c 2 2 JM- c 2 0. Then, we introduce Lemma 3.2 to evaluate the fitness of any given neural architecture.
Th = min(nn - n b b. c) E [0..
(2)
The other is the number of decision regions shaped as seg- ments that can be correctly formed by the m-th cell of æ, which is denoted as Jm and can be calculated by
Lemma 3.2 (Fitness Function). Given a neural architecture æ, its faness value for solving MCC can be calculated by
I (z) = -Arri (Im + 2r) + Arseg (J + 2r (x)) n
(6)
J min (n b} + min(n",. , max/b- n' 0}),
where Artri and Arseg denote the area of a triangle and a segment, respectively, and π is the area of the unit circle.
(3)
where the first term represents up to b B-type blocks for classifying the segments within the sectors Sec"". and the second term indicates that at most a + max(b - nz 0} A-type blocks are used to classify the segments in Seg" and the segments within the sectors Sec"". Consequently, Im E [0..2r].
Proof of Lemma 3.2. Let F F(x) denote the fitness value of architecture According to the formulation for the calcu- lation of classification accuracy (i.e., Eq. (1) in the main paper), we have
F(x) = (IM=L fm + (tr/M-Ar.) Ar.)) /T,
Next, we establish the relationship between the decision regions and the classification accuracy of a solution, based on the classification accuracy calculation shown in Eq. (1). The first term in the numerator of Eq. (1) reflects how many points belonging to class [1..M- - 1] are correctly classified by x. This related to the number of correctly classified triangles and segments (including those within sectors) that belong to classes [1..M- - 1J. respectively, denoted as
(7)
where fm represents the area of regions that are correctly classified by the m-th cell of ær π is the area of the unit circle, and π. /MM - -Ar, denotes the area of regions belonging to class M minus the area of regions that are misclassified by the (M 1) cell.
According to the parameter settings (as discussed in Section 2.1 of the main paper), the area of the regions that can be correctly classified by an A-type, B B-type, and C-type block is (0, Arwg), {0, Artii Argee) and (0, Artri), respectively. We note that a sector can be divided into a triangle and a segment, as Ar = Arsa + Argri. Since Ind and Jm represent the number of correctly covered triangles and segments, respectively, Vm E I..M- 11, we have
M
m E [0.. 1 2r],
(4)
M-
J2
mm E [0... 10--211 2r).
The second term in the numerator of Eq. (1) reflects how many points belonging to class M can be classified correctly by x. Any point in Sec M U Tri M can always be correctly classified, This because no blocks in x cover these points,
fm = 1Th Arui + pm A
In addition, there are & segments in class M that can be misclassified by the (M - 1)-th cell, so we have Ar. =
6

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
<x" Ar Arseg Therefore, Eq. (7) can be expressed as
In addition, according the second term in Eq. (6), i.e. Jn + 2r----e E [2r...], S; can be partitioned into (n (n-2r +r+11 1) sub-subspaces that are denoted as U - Sy where 8 { E S Le = i + 2r Ex j + 2r}. The following relationship exists between different sub-subspaces of Sy:
M-1
mm. AAri + J
Araeg
1
Are
F(x)
+
π
M
π
m=11
Artri
Arsug + M
1
Arseg
=Ig-
+ Js
cx"
π
S <g S <g S
<g S
1
+ (Ug Ar + (Jx- - -E))
Arseg)
M
π
where S <z S. represents that (xx < Fly) for all x E S/ and all y s4+1
where 1 Em=1 I and J. = Em=l J.m Since 2Mr and Arti + Arzeg = T/n, the lemma holds.
4. Runtime Analysis
To illustrate how the fitness function defined in Eq. (6) evaluates a solution, we provide a calculation example by using the neural architecture shown in Figure 2(b) as æ.
In this section, we analyze the expected runtime of (1+1)- ENAS for solving MCC. As the (1+1)-ENAS algorithm generates only one offspring solution in each generation, its expected runtime equals the expected number T of genera- tions to reach the optimum, which is denoted as [[[]].
In this case, we have ' 1, I = 6, Ja = 6, and Arsec Artri + Arseg π. n.. By substituting these into Eq. (6), we can yield the same accuracy of 0.83.
The mathematically formulated fitness function in Eq. (6) demonstrates that the fitness of æ can be improved by ap- propriately increasing the number of A-type, B-type, and C-type blocks in each cell, as these contribute positively to both II 2r and J. + --2r-ca Cz. which correspond the num- ber of correctly classified triangles and segments (including those within sectors) for classes I to M, respectively. This behavior is somewhat similar to the ONEMAX benchmark function for EAs, allowing it to play the role of ONEMAX in ENAS.
4.1. One-bit Mutation
We prove in Theorems 4.1 and 4.2 that the upper and lower bounds on the expected runtime of (1+1)-ENASonell solving MCC are E = O (rM In(rM)) and E[T] = M2r In M). respectively. Note that (1+1)-ENASonel) refers to (1+1)-ENAS using one-bit outer-level mutation and either local or global inner-level mutation.
Theorem 4.1. (Upper bound) The (1+1) ENASoeets algo- rithm needs E[T] = O (r In( to find the optimum for Mcc.
3.3. Search Space Partition
Theorem 4.2. (Lower bound) When the upper bound s on the number of each type of block in the initial solu- tion is r, the ENASS-NNsoouebal algorithm needs E[T]] Mr M) to fond the optimum for Mcc.
In the runtime analysis of EAs, it is common to construct a distance function to investigate the progress of the algo- rithm (Auger & Doerr, 2011; Neumann & Witt, 2010; Zhou et al., 2019; Doerr& & Neumann, 2020). The partitioning of the search space plays a key role in defining the dis- tance function. The runtime analysis of ENAS follows the conventional analysis approach. Therefore, we present partition of the search space designed in Section 2.2, which can facilitate the runtime analysis of ENAS solving McC.
Before proving Theorem 4.1, we briefly outline the main idea of the proof. We divide the optimization procedure into two phases, where the first aims at finding one solution that belongs to Sn-2r. and the second aims at finding one optimal solution that belongs to S For each phase, we utilize the multiplicative drift analysis (Doerr al., 2012) to derive its expected runtime. This widely used mathematical tool is well-suited for cases where the expected progress is proportional to the current objective value, as observed during the proof process. To utilize this tool, we construct a distance function V(.) for each phase to measure how far a solution is from the target solution of the phase. For the simplicity of presentation, we let 2r = -2r(M - 1) be expressed as N, Ya,5' denote the probability that I = i changes to 1 = i' after the inner-level mutation, and 72,=' be the probability that Jn e increases by z' after the inner-level mutation.
Let S denote the search space, which also refers to the solution space. According to the first term in Eq. (6), i.e., lee + 2r [2r..)). S can be partitioned into n - 2r + subspaces that are denoted as U where S; = {x E S I. + 2r- i )r). The following relationship exists between the subspaces:
So <g Si <g < <g Sa-2r;
where S; <. S represents that F F(x) < Fly) for all x E S; and all y E S.41. The basis for the partition is that the fitness function in Eq. (6) is dominated by the Ig term, as Arui > (n - 2r)- problem.
Arseg where n 2 8 in the McC
In addition, to identify which cells contribute to progress toward the optimum, we utilize a bit-string of length M
7

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
to characterize whether each cell's I (or 3e matches the optimum or not, denoted o for y.... 1 E {0, 11 where 6 (m < M 1) can be expressed by
where the second inequality holds by lo/u - -- 2
M - 1 - Tax / (derived by Eq. (8)) and 7r 2 2/9 (Lv et al. (2024b) showed that: if the inner-level mutation adopts the local mutation, 16,++ 2 2/9 as shown in their Lemma 3; if the inner-level mutation adopts the global mutation, 7a,++1 2 0.23 as shown in their Lemma 5). In other words, the drift of Vi (axx) is bounded from below by o (xx) with o 2/ Note that (1x) = N Lg.
[1 if (Ie N, _ = 2r) or (Ix JT 2r),
t0 if (Im < N, M < 2r) or (Im J < 2r),
and oM-1 1 when (Ig < N.
r) or (Le
N,J 2r, cx 0): otherwise, 0N1-1 0. The number of cells that math the optimum is given by the number of 1-bits in the binary string denoted as |o]: = EM oth Then, lo/o denotes the number of O-bits. Given any neural architecture with Ig we have the bounds of Jo]1, i.e.,
Owing to 0 < N during the first phase, the distance of the initial individual is (0o) E [1...V - -1]. By the mul- tiplicative drift theorem (Doerr et al., 2012), the expected runtime of finding a solution with V1= = 0 (i.e., I = N) is O(11 + In (/(z)))/oo = O (N
Phase After the aforementioned phase, we pessimistically assume that the searched solution with Jz 0, which means that |o] = 0. As the goal of the second phase is to reach Jæ < N, we construct new distance function 12(2)) = N - (Jæ cx)) It is easy to verify that V2(x)) = 0 if and only Ja - Exz = N.
i 2r'
max - (M- 122 < |0|
where the upper bound holds by the maximum value of Im being 2r, and the lower bound is occured when Vm 1 2 2r-1. Given Ja = j and Ja (x 2, we have |o| S [(- J (22r] LJ
(j- (j- [2) S 22r).. The
The analysis is similar to phase One difference is the constant probability T2,,'' which is lower bounded by 1/9 as shown in Lemmas 4 and 5 of (Lv al., 2024a). Similar to the calculation in Eq. (9), the expected one-step progress in V2(22)) is at least (Vz - |o] 2 M - multiplicative drift, the expected runtime for the second phase is O(N In N)). By combining the two phases, we get E[T] E (rM In(rM)) because N 2r(M 1).
bounds will be utilized in the proofs of Theorems 4.1- Next, we proceed to establish the proof for Theorem 4.1.
Proof of Theorem 1. According to the partition of search space, we divide the optimization procedure into two phases, and we pessimistically assume that the solution with J > 0 is not found in the first phase.
(1/9) since lolo = M 1 - (Ja,, (2rr.. By utilizing the
Phase 1: This phase starts after initialization and ends when a solution x with T = n 2r is found, i.e.,
x E Sp-2r.
The proof idea of Theorem 4.2 is that the initial solution has (M -1)/r O-bits in o with probability at least 1/2, and then (1+1)-ENASonobi requires at least Q(r In M) expected runtime to find the solution belonging to Sn-2e 22- This is because the probability that at least one of these O-bits in o of the initial solution remains unchanged over max (1, M - -2} In(M 1) generations is lower bounded by 1 - -1, The complete proof of Theorem 4.2 is provided in Appendix C.1.
Phase 2: This phase starts after Phase 1 and ends when a solution a E S is found.
Phase 1. We define the distance function (xx) = N- Ia = -M1 (2r- ) to measure the progress towards the optimum in the first phase. It is easy to verify that (zx) = iff T = N. To make progress, it is sufficient to select one cell with TTT by executing the inner-level mutation (local or global). The probability of the former event (selecting one cell with Tt 0) equals lolo/ (M - 1) since there are |olu cells with om = O. Hence, the probability of making progress is at least (lolo/ - 1))- 71,41 In this case, the distance V12 can decrease by at least
and make the value I increase
4.2. wis- Mutation
Next, will show that by replacing one-bit with bit- wise mutation, the (1+1)-ENAS algorithm can achieve a similar runtime. In particular, we prove in Theorems 4.3 and 4.4 that the upper and lower bounds on the expected runtime of (++I)-ENAbbitiie solving McC are ETT = (r In(rM)) and E[T] Q(r In M). respectively. Note that (1+1)-ENAS, pe denotes that (1+1)-ENAS uses bit-wise luter-level mutation and either local or global inner- level mutation.
Then, we analyze the expectation of the one-step progress (i.e., drift) towards the target solution in the first phase. We have
(xx) - (((4111) [xx)]]
1
Ix;
2
(9)
Theorem 4.3. (Upper bound) The (L+I)-ENASpttwil algo- rithm needs E = (M) to find the optimum
2
M --1 7h,1411 1
1-
N
g'
8

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
for MCC.
The above experiment results also offer practical guidance for mutation design in ENAS. In particular, many ENAS algorithms adopt bit-wise mutation (also called fit-flip mu- tation) (Xie & Yuille, 2017; Pan et al., 2024; Yan et al., 2024), which requires manual setting of an appropriate flip- ping probability; whereas the one-bit mutation, which is simpler in use, can be initially considered in the design of ENAS algorithms. This finding is particularly effective for block/cell- search spaces, where one-bit mutation could achieve significant changes in neural architectures. This helps explain its adoption in practical ENAS methods like AE-CNN (Sun et al., 2019b), which utilize single-step mutation (functionally analogous to one-bit bit mutation) as their core search operator. To further strengthen our find- ing, we extend our experiments to population based ENAS algorithms with crossover. Due to space limitations, the experiment results are included in Appendix D.
Theorem 4.4. (Lower bound) When the upper bound
on the number of each lype of block in the initial solu- tion is v, the (1+1)-ENASptwia algorithm needs [[[]] = M In M) to find the optimum for McC.
The main proof idea of Theorem 4.3 is similar to that of Theorem 4.1, i.e., partition the optimization procedure into two phases and analyze the runtime of each phase. One dif- ference is the calculation of the bound on the probability of generating better offspring solution than a parent solution. The probability of each cell selected by the outer-level muta- tion in one round is 1/(M 1). Thus, we have that the algorithm can decrease the distance Vi (or V22) by at least one with probability at least p. -V,++1 - (1 - M- -looo (or "2,,"' (1 - p)M lolo). Then we can derive the one-step progress for each phase, and conclude that the ex- pected runtime to find the target solution is Or In(r The proof of Theorem 4.4 similar to that of Theorem 4.2. The complete proofs of Theorems 4.3 and 4.4 are provided in Appendix C.2 and Appendix C.3.
6. Conclusion
In this paper. we take the first step towards the runtime anal- ysis of the ENAS algorithm for solving multiclass classifi- cation problems. We begin by proposing multiclass clas- sification problem MCC, and mathematically formulating fitness function for this problem to serve as benchmark for the runtime analysis of ENAS. Furthermore, we design a two-level search space with cells at the first level and blocks at the second, which is consistent with the practical ENAS algorithms and also enables theoretical research. Based on both designs, we analyze the expected runtime bounds of the (1+1) -NNSS algorithm with one-bit bit-wise mutation for solving MCC, and prove that the algorithm using both mutations can achieve the same expected runtime bounds.
5. Experiments
In this section, we investigate the empirical performance of the (1+1)-ENAS algorithm with four different mutation settings for solving McC. We set the problem classes M from 2 to 24, with step of 2, and the problem parameter from 2 to 10, with a step of 2. Figure 3 presents the average number of generations of 1,000 independent runs for find- ing an optimal solution. It shows that both local and global inner-level mutations can achieve similar performance. Fur- thermore, using one-bit or bit- bit-wise outer-level mutations has little effect on performance, typically resulting in con- stant factor difference. These empirical results are generally consistent with Theorems 4.1 to 4.4.
The results suggest that a simple one-bit mutation can be ini- tially considered in the ENAS community. As a foundation for the above theoretical research, the proposed benchmark Mcc narrows the gap between previous theoretical analyses and practice.
x10'
10
x1o"
M 20
Averge nimber of peneratioon
Avenpe pumbeer gf gcooeettoo
andirrieal ondtii pival
Building on this work, more theoretical works on ENAS are left to be done, including but not limited to the following aspects: 1) analyzing more advanced evolutionary mecha- nisms/operators, such as population mechanisms, crossover operators, and stochastic selection mechanisms, to help the design of more efficient ENAS algorithms; 2) consid- ering more realistic scenarios, such as noisy optimization, dynamic optimization, and multi-objective optimization; 3) extending to more challenging multi-class classification with richer decision boundaries, such as diverse polyhe- dra regions beyond sectors or triangles, to assess ENAS's capability in constructing blocks with diverse topologies.
matee globl
basiserlae hakise-glhh
litiseeeed Mialie-glohll
0
15
25
Problem classes
Valuer
(a) Fixed r 10. varying M
(b) Fixed M 20, varying r
Figure 3. Average number of generations of the (1+1)-ENC ENAS algo- rithm with different mutations for solving the McC problem. The legend identifies mutation types: the term hefore the symbol " denotes the outer-level mutation, and the term after the symbol represents the inner-level mutation.
9

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Impact statement
Elsken, T., Metzen, J. H., and Hutter, F. Neural architecture search: A survey. Journal of Machine Learning Research, ((1)::197-20117,
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Fischer, P., Larsen, E. L., and Witt, C. First steps towards a runtime analysis of neuroevolution. In Proceedings of the 17th International Workshop on Foundations of Genetic Algorithms (FOGA'23), pp. 61-72, Potsdam, Germany, 2023.
Acknowledgments
The authors want to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Natural Science Foundation of China (No. 62276175 and No. 62276122 244) and Innovative Research Group Program of Natural Science Foundation of Sichuan Province (No. 2024NSFTD0035).
Fischer, P., Warwicker, J. A., and Witt, C. A runtime analy- sis of bias-invariant neuroevolution and dynamic fitness evaluation. In Proceedings of the 26th Annual Conference on Genetic and Evolutionary Computatioo (GECCO 24), pp. 1560-1568, Melbourne, VIC, Australia, 2024.
Friedman, J., Hastie, T., and Tibshirani. R. Additive logistic regression: A statistical view of boosting (with discussion and a rejoinder by the authors). The Annals of Statistics, 28(2):337-40) 2000.
References
Aly, M. Survey on multiclass classification methods. Neural Netw, 19(1-9):2, 2005.
Gibson, G. J. and Cowan, C. On the decision regions of multilayer perceptrons. Proceedings of the IEEE, 78(10): 1590-1594, 2002.
Auger, A. and Doerr, B. Theory of Randomized Search Heuristics Foundations and Recent Developments. World Scientific, Singapore, 2011.
Bertsimas, D. and Tsitsiklis, J. N. Introduction to Linear Optimization. Athena Scientific, 1997.
Grandini, M., Bagli, E., and Visani, G. Metrics for multi-class classification: An overview. arXiv preprint arXiv:2008.05556 2020.
Doerr, B. and Goldberg, A. Adaptive drift analysis. Algorithmica, 65:224-2500 2013.
He, X., Zhao K., and Chu, X. Automl: A survey of the otate-of-the-art. Knowledge-Basee Systems, 212:106622, 2021.
Doerr, B. and Neumann, F. Theory of Evolutionary Com- putation: Recent Developments in Discrete Optimization. Springer, Cham, Switzerland, 2020.
Kratsch, S., Lehre, P. K., Neumann, F., and Oliveto, P. Fixed parameter evolutionary algorithms and maximum leaf spanning trees: matter mutation. In Proceedings of the I 11th International Conference Parallel Problem Solving from Nature (PPSN' 10), pp. 204-213, Kraków, Poland, 2010. Springer Berlin Heidelberg.
Doerr, B., Jansen, T., and Klein, C. Comparing global and local mutations bit strings. In Proceedings of the 10th Annual Conference Genetic and Evolutionary Computation (GECCO 08), pp. 929-936, Atlanta, GA, 2008.
Liu, H., Simonyan, K., Vinyals, O., Fernando, C., and Kavukeuoglu, Hierarchical representations for ef- ficient architecture search. In Proceedings of the 6th International Conference of Learning Representation (ICLR' 18), Vancouver, BC, Canada, 2018.
Doerr, B., Johannsen, D., and Winzen, C. Mul- tiplicative drift analysis. Algorithmica, 64(4):
673-697, 2012. ISSN 0178-4617. doi: 10.1007/ 500453-012--622xxx URL https: httd/di.oo////// 00055333-112-222---
Liu, Y., Sun, Y., Xue, B., Zhang, M., Yen, G., and Tan, K. C. A survey on evolutionary neural architecture search. IEEE Transactions on Neural Networks and Learning Systems, 34(2):550-577 2023.
Droste, S., Jansen, T., and Wegener, I. On the analysis of the (I+1) evolutionary algorithm. Theoretical Computer Science, 276(1-2):51 2002.
Durrett, G., Neumann, F., and O'Reilly, U.MM. Compu- tational complexity analysis of simple genetic program- ming on two problems modeling isolated program se- mantics. In Proceedings of the 11th Workshop on Foun- dations of Genetic Algorithms (FOGA'11), pp. 69-80, Schwarzenberg, Austria, 2011.
Lv, Z., Bian, C., Qian, C., and Sun, Y. Runtime analysis of population-based evolutionary neural architecture search for a binary classification problem. In Proceedings of the 26th Annual Conference on Genetic and Evolution- ary Computation (GECCO'24) 24), pp. 358-366, Melbourne, VIC, Australia, 2024a.
10

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Lv, Z., Qian, C., and Sun, Y. A first step towards run- time analysis of evolutionary neural architecture search. arXiv:2401.11712, 2024b. URL https://arxis:
So, D., Manke, W., Liu, H., Dai, Z.., Shazeer, N., and Le,
Q. V. Searching for efficient transformers for language modeling. In Advances in Neural Information Processing Systems 34 (NeurIPS'2I), pp. 6010-6022, virtual, 2021.
Miikuulaienn, R., Liang, J.. Meyerson, E., Rawal, A., Fink,
Sudholt, D. A new method for lower bounds the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 1783):418-33,,
D., Francon, O., Raju, B., Shahrzad, H., Navruzyan, A., Duffy, N., et al. Evolving deep neural networks. In Artifi- cial Intelligence in the Age of Neural Networks and Brain Computing (Second Edition), pp. 269-287, Academic Press, 2024.
2013. 2013.
Sun, Y.. Xue, B., Zhang, M., and Yen, G. G. Completely au- tomated CNN architecture design based on blocks. IEEE Transactions on Neural Networks and Learning Systems, 31(4):1242-1254, 2019a.
Neumann, F. and Witt, C. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Com- putational Complexity. Springer, Berlin, Germany, 2010.
Sun, Y., Xue, B., Zhang, M., and Yen, G. G. Evolving deep convolutional neural networks for image classification. IEEE Transactions on Evolutionary Computation, 24(2): 394 2019b.
Neumann, F. and Witt, C. On the runtime of randomized local search and simple evolutionary algorithms for dy- namic makespan scheduling. In Proceedings of the 24th International Joint Conference on Artificial Intelligence 15), pp. 3742-3748. Buenos Aires, Argentina, 2015.
Ünal, H. T. and Başçiftęi, F. Evolutionary design of neural network architectures: review of three decades of re- search. Artificial Intelligence Review, 55(3):1223-1802 2022.
Nguyen, Q. Mukkamala, M. C., and Hein, M. Neural networks should be wide enough to learn disconnected decision regions. In Proceedings of the 35th International Conference on Machine Learning (ICML'18) pp. 3737- 3746, Stockholm, Sweden, 2018. PMLR.
Wegener, I. Methods for the analysis of evolutionary al- gorithms on pseudo-Boolean functions. In Evolutionary Optimization, pp. 349-369. Springer, 2003.
Pan, W., Zhao, F., Shen, G., Han, B., and Zeng, Y. Brain-inspired multi-scale evolutionary neural architec- ture search for deep spiking neural networks. IEEE Trans- actions on Evolutionary Computation, 2024.
Witt, C. Tight bounds on the optimization time of random- ized search heuristic on linear functions. Combinatorics, Probability and Computing, 22:294-318, 2013.
Qian, C., Yu, Y., and Zhou, Z.-H. Variable solution structure can be helpful in evolutionary optimization. Science China: Information Sciences, 58(1 (0:(111)117, 2015.
Xie, L. and Yuille, A. Genetic CNN. In Proceedings of the IEEE International Conference on Computer Vision (ICCV'17), pp. 1379-1388, Venice, Italy, 2017.
Qian, C., Liu, D.-X., Feng, C., and Tang. K. Multi -bjeitobeecttve evolutionary algorithms are generally good: Maximizing monotone submodular functions over sequences. Theo- retical Computer Science, 943:241-266 2023.
Yan, X., Huang, H., Jin, Y., Wang, Z., and Hao, Z. Neural architecture search based on bipartite graphs for text clas- sification. IEEE Transactions on Neural Networks and Learning Systems, 2024.
Real, E., Moore, S., Selle, A., Saxena, S., Suematsu, Y. L.,
Yang, S., Yu, X., Tian, Y., Yan, X., Ma, H., and Zhang, X. Evolutionary neural architecture search for transformer in knowledge tracing. In Advances in Neural Information Processing Systems 36 (NeurIPS'23), pp. 19520-19539, New Orleans, LA, USA, 2023.
Tan, J., Le, Q. V., and Kurakin, A. Large-scale evolution of image classifiers. In Proceedings of the 34th Interna- tional Conference on Machine Learning (ICML'I7) pp. 2902-2911, Sydney, Australia, 2017. PMLR.
Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regular- ized evolution for image classifier architecture search. In Proceedings of the 33th AAAI Conference Artificial In- telligence (AAAI'19), pp. 4780-4789, Honolulu, Hawaïi, USA, 2019.
Zhong, Z., Yan, J.. Wu, W., Shao, J., and Liu, C.-L. Practical block-wise neural network architecture generation. In Proceedings of the 35th IEEE Conference on Computer Vision and Pattern Recognition (CVPR' 18), pp. 2423- 2432, 2018.
Sharma. S., Sharma, S., and Athaiya, A. Activation func- tions in neural networks. International Journal of En- gineering Applied Sciences and Technology, 4(12):310- 316, 2017.
Zhou, Z.-H., Yu, Y., and Qian, C. Evolutionary Learning: Advances in Theories and Algorithms. Springer, Singa- pore, 2019.

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Zoph, B., Vasudevan, V., Shlens, J., and Le, Q. V. Learning transferable architectures for scalable image recognition. In Proceedings of the 35th IEEE Conference Computer Vision and Pattern Recognition (CVPR'18), pp. 8697- 8710, Salt Lake City, UT, USA, 2018.
12

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
A. Neural Architecture
A.1. Details Parameter Settings
Parameters of the binary neurons within the block. The weight i and bias binary neuron corresponds to the angle of the unit normal vector for the hyperplane and the distance from the origin, respectively (Fischer al., 2023). We assume that the parameters, i.e., the weight yp and bias, satisfy the following conditions:
The bias of the neuron in an A-type block set as cos( con)./
The bias of the neurons in a B-type block is set O, and the difference in yp between these neurons is (* 2x/n) or (πt 22t/n).
Two neurons in a C-type block have a bias of 0, with y difference (æ + 2 has bias of cos(a//v //n) and a difference with the other two neurons of ( 22/22 + z/n) or (3T/2 /2 x/n).
/n) ) or (T - 2n /n). while the third neuron
Existing optimization method can theoretically guarantee the optimality of the remaining parameters, c.g., of each binary neuron and difference.
Parameters for each type of block are depicted in Figure
B
πI
bias COS 12
@
Stas
COS
12
3π
7n Φ 12
2πT n
191
L2l 2 n
1Φ2 93
1Φ2 Φ11
2
n
2TT
1Φ2 - P1 = π
n
Figure Visualization of the parameter settings for A-type, B-type, and C-type blocks, along with corresponding decision regions generated by each block type, upon the McC problem (M = 3, 2, 12). The red arrow represents the unit normal vector of a hyperplane (linc), with weight o as its angle. The bias is the distance of the hyperplane to the cirele's 's center. Each block's arrows collectively point to the region produced (covered/bounds) by that block. The black- regions are incorrectly classified by the specific block. (a) Tof-left: The decision region (a segment region Syee) produced by an A-type block with its single binary neuron's bias 72/12. (b) Top-right: The decision region (a sector region $ produced by B-type block, where both neurons have a bias of 0, and the difference hetween the neurons is (422 9pi = + 2 n = 7 This decision region is generated by (c) C-type block, where the binary neurons, each with bias of have 2nt 5x 5x/6, and their differences with the third binary are [pp spl 2/2 + π /nn = 7m11
of cos(m/n /n) and
Bottom:
The decision region triangle region Sex)) produced
a difference of 1y22 -pl
and |02 Pal 3t/ /2 x x/n- 17x 12, respectively.
Parameters of the neurons (N1, .2,..., .N in hidden layer. Figure 5 shows the weights and biases of these neurons. Specifically, neuron N, has two inputs with weights of {1, 0.43, neuron NM has a single input with a weight of 0.5, and each the remaining neurons (i.c., N2..., NM--1) has three inputs with weights of {0.5, 1, 0.4.. Additionally, the bias for neuron M 0.1, whereas all other neurons in (N1, N2...., NMr have bias of O.
13

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
D₁
Call
N1
0.4
0.5
b2
C
1
N2
0.4
0.5
3
1
D3
0.4
N 3
0.5
0.4
0.5
bx-1
Call M
1
N MM-1
0.5
bm
0.1
N M
Figure 5. Parameters (weight and bias) of the neurons in (N1, N2,-.., Nos..
A.2. Decision Regions
Based on the above parameter settings, it is clear that when the dataset on the unit circle, three types of blocks in the neural architecture generate decision regions with distinct shapes. Specifically, an A-type block in the neural architecture produces sector-shaped decision region, as shown in the top-left example of Figure 4; B-type block produces a sector-shaped decision region, shown the top-right example of Figure 4; and C-type block produces triangle-shaped decision region, shown in the bottom example of Figure Overall, A-type blocks only produce the segments (including the segments within the sectors), B-type blocks can produce the triangles and sectors, and C-type blocks can produce the triangles (including the triangles within the sectors).
In addition, since the utilization of hidden layers (i.e., neurons (N1, N2,..., Nas }), each block in the m-th cell will only form decision regions belonging to class m, except for the segment region that might incorrectly classified as class (M + m 1) mod M. This exception occurs because, in the ((M + m 1) mod M)-th cell, a B-type block used to form the triangle region S E (M+-1= mod instead of a C-type block, which leads to the incorrect coverage of segment region Si connected with Si. where Si belongs to class m (according to the third characteristic Mcc shown in Section 3.1 of the main paper). However, once an A-type block in the m-th cell used to cover St the neural architecture can ultimately classify all of the points in S correctly. For further discussion on how the neural network classifies correctly in this case, please refer to the classification examples provided Appendix B, particularly for the case where the input instance x E STeg-
B. Examples for Neural Architecture Solving Mcc
To detail how the neural architecture solves McC, utilize the example of Mcc (M and r 2) in the main paper to give an explanation. Table 1 illustrates several input instances along with the corresponding classification process and results. Specifically, this table includes the outputs of cells, neurons in N2,,N2,... . NM J. softmax layer, the final classification results, and whether classifications are right or not for seven input instances. Rows 1-2 present the classification process and results for input instance labeled as class 1, with three regions whose points will be misclassificd; rows 3-5 show the classification process and results for input instance labeled as class 2, with two regions misclassified; rows 6-7 display
14

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Table Examples for testing the performance neural architecture {(0, 3, 0): (1,3, 0)), including classification tests for seven input instances in MCC (M = 3 2). The first column lists the case number. while the second and third columns display the seven input instances and their corresponding labels, respectively. Columns 7 provide the outputs from cells, neurons in (N1, N2,... ........ N J. softmax, and the final classification results. The bolded numbers in columns 5 and 6 represent the maximum values among its output. For each case, the output of the softmax layer a set of probabilities (i.e.. [Pi: P2, }3)) with the class corresponding to the maximum value being the classification result. Column presents whether the neural architecture correctly classified the input instance; it shows "V" if the classification correct (i.e., its label and classification result the same), and "X" if it is not.
Cells
N2, Na) Nat Output
Softmax Layer
Classification
Input Instance æ
Label
Right?
Output
Output
Result
1 E Sec U Sec U S
10
{1.0, 0.5, 0.1}
{0.50, 0.30, 0.20}
Class 1
Class 1
2 É Seg U Sin U S
00
(0.0. 0.0, 0.1)
(0.32, 0.32, 0.36)
Class 3
x
3 é Sac U Sac U USH
01
(0.4, 1.0. 0.6]
{0.25, 0.45, 0.30
Class 2
4 E Sin U Speg
Class 2
00
{0.0, 0.0, 0.1
{0.32, 0.32, 0.36)
Class 3
x
5 x E Seg
(1.4. 1.5, 0.6)
{0.39, 0.43, 0.18)
Class 2
6 x E Sac U Sac U Utn
ii US U S
00
(0.0, 0.0, 0.1}
{0.32, 0.32, 0.36)
Class 3
Class 3
7
E $1
(0.4, 1.0, 0.6)
{0.25, 0.45, 0.30)
Class
x
the classification process and results for input instance labeled as class 3, with one region misclassified. The classification accuracy, calculated as the ratio of the area of correctly classified points to the area of the circle, is approximately 0.83.
C. Proofs
C.1. Proof of Theorem 4.2
Proof of Theorem 4.2. Similar to the proof of Theorem 4.1, we begin the proof by analyzing phase 1.
We first show that the expected number of 0-bits and 1-bits in the initial solution 2p is 1zo lol = (M 107-1)11 1)(1 1011-117 1//r2) and Bl [i] = (M - 1)/r", respectively, where Oz, represents o of æo.
Let P(oT" 1) be the probability that the m-th cell of the initial solution has !n, 2r B-type and C-type blocks. Since both ng and nž drawn from the uniform distribution U[1, r]. the probability of ny n 2r (i.e., 0 1 for the initial solution since I 2r) is 1/r², and the probability of n - no 2r (i.e., o% = 0) is 1/r2. Then, we have P(o = =1 = 1/r2 and P = 0) = 1 - 1/r2 2 for the initial solution. Thus, the expectation of |o] for the initial solution is (M 1)/r2.
By Markov's inequality, an initial solution has at least = -M 1)/r 0-bits in Ow, with probability
P P(lozo g) = P P(O00l < (M - 1) - g)
(1oxo 11 2 (M 1) g)
E [1]
> (M - 1) -9
(10)
(M 1)/1²
2
2 1/2,
(M 1)
12 -
where the last inequality holds by r 2
15

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
Next, we show the expected runtime for finding solution in subspace 2n- i.e.,
(M-1)-1
E
E
Σ
E Ozo lo =d] P( d)
d=0
(M (M-1)-1
2
Σ
E 00 lo = =d]- e( =d)
(II)
2 [
P( 10 = - 2 g)
= [ |0zalo 1- - 2 t P > t)/2,
where P(T1- > t) is the probability that the generations for finding solution in S is greater than t.
Let G denote the event that at least one of these g O-bits in Oza is never changed t = max 1, M - 2} In(M 1)- r. We show that the event G' happens with probability lower bounded by 1 - e__ Let 1 - -k.+i / - 1) describe the probability that a new B C-type block would not be generated for the cell with 0 where ",,4+1 is constant probability which detailed in the proof of Theorem 4.1. Then, the probability that the value I of specific cell with 6Tn O in the initial solution 2n is never increased in f generations is (1 7 1))² So, the value m of specific cell with T 0 in the initial solution Øo is increased by at least once in / generations with probability 1 - (1 71.+1((M 1))². Furthermore, any of these cells corresponding to a 0-bit in Oz, is increased by one at least once in t generations with a probability of (1 - (1
one round (i.e., value In" is not increased),
1aa///MMM)1))) Thus, we have
M 2 9
))
1 (1
P(G) =1
1)-r) M-1
max(1,M-22--0)
1
2
M -1
21-6
Combining with Eq. (11), the lower bound of the expected runtime for the first phase can be derived by
E[Ti] 2 t- P(T1 > t)/2
2 max 11 M - 23 II(M - 1) -r- P(G)/2
2 max(1, [1 M 23 In(M 1) .r (1 - -e- 1/2
E InM.
Because the generations T, of phase is a lower bound on the generations T of the whole process for finding an optimal solution belonging to S7-2r, we have [E[T]= (2 In M).
C.2. Proof of Theorem 4.3
Proof of Theorem 4.3. Since the one-bit and bit-wise mutations have the same lower bound for the probability of increasing the value of Le (or Jæ) by 1, we can obtain the same lower bound for the expected one-step progress (drift). Specifically, the drift of Vi (2x) (or Vz(2:)) ) is bounded from below by a V1 (xx)) (or a Vz(x))) with a = 2 2/99) (or a = 1/(9))).. These results lead to the same upper bound results for the expected runtime, i.e., O(r M)). by utilizing the multiplicative drift analysis (Doerr al., 2012). Therefore, similar proof refers to the proof of Theorem 4. the main paper.
Here, present the proof with another approach that uses the fitness-level technique (Wegener, 2003; Sudholt, 2013). which also yields the same theoretical result.
Let P. denote the lower bound on the probability of the algorithm creating a new solution in Up Sp, provided the algorithm is in S,. The most optimistic assumption is that the algorithm makes it rise one level (i.e., 1y41). To make jumping from Sy to S141 successful, it is sufficient to select one O-bit (denote as the m-th cell) from o by bit-wise mutation and mutate the m-th cell to increase its value Im by one through inner-level mutation, which happens with a probability
16

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
of भ oo1o 7,,+1. Meanwhile, the other 0 and bits are either not selected or their corresponingg l values remain unchanged after being mutated, which happens with a probability of at least (1 - M- (MM-)) 2 1/c. Thus, we have
1
P1 2
M 10/0
7 1
1 2
2
c
N
9c
where the last inequality holds by |o/o 2 M ---1-1
- (2r) (derived by Eq. (3) in the main paper), N = n- = 22r(M 1),
and 71,++1 2 2/9. Thus, the expected runtime for the first phase
N-1
N-1
B
Σ
9e
P1
2
1 1-
I/N
I=0
1=0
N-1
9e
9e S NINNE0(MM(MM) 2
N
2
N -
1=0
Then, we analyze the second phase. Before beginning the analysis, it is important to note that Jlx Ex 2 0 for any solution a. This is because <a will only be positive if the (M -1 1)-th cell contains more than r B-type blocks (leading to J 2 r since J JM 2 r), which allows for n2j > 0 B-type blocks to cover triangles belonging to class M - 1, making cg > In this case, we have In fm 2 0 since J 2 r and 6 S r. In all other cases, where 6 = 0, we have In 6 2 0 since Jæ 2 0. Therefore, we have Ja Ex = J r 2 0, given that the algorithm is in S (i.e., x E 8/²).
Next, we continue the analysis of the runtime for the second phase. Since 77,.++1 2 1/9 as shown in the proof of Theorem 4.1, we can derive that the lower bound on the probability of jumping from S to S SJ-1 is 11.=+1/(MM 1) lolo/e 2 (1 - (J r)/N)/(9e), where 0/0- = .M- - 1 - [o) 2 M - 1 (J - -r)/(2r) and J - rr 2 O. Then, similar to the first phase, we have the expected runtime for the second phase is E[Tp] E O(r Mn))
By combining the two phases, we get E[T] E O In(MM).
C.3. Proof of Theorem 4.4
Proof of Theorem 4.4. Similar to the proof of Theorem 4.2, the probability of the event that the algorithm generates an initial individual we with (M- - 1)/r O-bits in o is lower bounded by 1/2. For specific cell with 0 = 0, the probability of the event that the number of B-type and C-type blocks in this cell increased is bounded by Σe Er=141 Y,. (M -1 1) = 1/(M 1). Then, the proof follows similar approach to that of Theorem 4.2. The event that at least one of the cells with T
in
an is never changed in f = max (1, M 2}- In M - 1) r generations happens with probability exceeding (1 - (1-e- -) Thus, the probability of the event that the generations for finding solution in Sn is greater than is lower bounded by (1 ---e- ----e-l ')). Starting from the initial individual øe, the algorithm finds solution in subspace Sn-2r is O(r In M) according to Eq. (11). Because the generations of phase is a lower bound on the generations 7 of the whole process for finding an optimal solution belonging to Sm-2r,, we have E[T]- = 2(r In M))
D. Extended Experiments
To further strengthen our findings, we extend the experiments Section 5 to three SOTA ENAS algorithms: (A+A)-ENAS with mutation only (A (2, 4, 10)), which is adopted in methods like LEIC (Real et al., 2017) and AmoebaNet (Real et al., 2019); one-point crossover-based ENAS, which is adopted in CNN-GA (Sun et al., 2019a) and ENAS-KT (Yang et al., 2023); and uniform crossover- based ENAS, which is adopted in Genetic CNN (Xie & Yuille, 2017). All experiments follow the same problem settings as in Section 5, and the results are presented in Figure 6 and Figure 7. The results show that oie-bit mutation achieves comparable runtime performance to bit-wise mutation on the McC problem.
17

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
2-2-ENAS i--
(2-2-ENNA oncrainCrreeveer
(2-2)ENAS Undforsrrrawvetee
mouhh-g35hu) batsecc globa)
0.-
biterret bnderacrgiohe glcbal
bakssee bikstscrglohal -gr
Ausegg gratrationn
0.4
0.-
Probiem daas
clanes
Probian clasce
(6mi) ENAS -
(4+4) ENAS CreeaaCrrrnaan (0)
X10
(4-4) ENAS, UnlfonrCrooveeiie (r-
16-
unctral plnna
enchet glohu
enctet (ponal
1.0
lutvioergiséel
bdbviccralsbe
bitkiserglobel
0.5
0.6
0.4
Probiem clance
Prebiem clasne
Prebicm clanex
x100
(10- 100-10-NNAS- (ru m0
X10' ([0-10) ENAS, saoPPiiuhhoooee i 10g
x10' ((HLE)-NNAS, L'iDeeCeossrrr (ra
1.6
1.4
aadiatabbcal
holvisergiskel
1.4
1.0
eadatmppordd
biwiseegllbel
1.2
0.5
0.8
0.6
0.4
0.2
02-
clases
Problem clanes
Probian clascs
Figure 6. Average number of generations of the ENAS algorithms with population and crossover for solving the MCC problem (r = 10. varying M). The ENAS algorithms include (A+A)-ENAS algorithm (with mutation only). (A+A)-ENAS algorithm with one-point crossover, and (A+A)-ENAS algorithm with uniform crossover, where À {2, 4, 10).
18

---

Runtime Analysis of Evolutionary NAS for Multiclass Classification
2-2-ENAS (V
X:0
(2-2-ENAS endPainkremeeeer (M
(2-2-ENNA UnaformCrrosvve (A4
mouhh-g55hu batsecc global
granstts
brksssc global
Valaer
(6m@)ENAS ENAS (20
Xtd
(g-i) ENAS LweeeisaCossue (M-
x10 (4-4) ENAS, UnaoonrCooovee (A5=20)
unctral glnnal
enchet glohu
endet (pona) -2-
lutviocrgiskel
batvicrallbel
bikiserglobel
Valoe
Valser
Value
x100
(10- 100-10-ENASS (M 201
x100 (10-10) ENAS www.Phlttrreeaeeroooooooo (M=2
x1e (DHLEHENNSS TWDeerCesssr (M-200
uadiatabbcal
asdietralubal
eadatmppord
1.2
holvisergiskel
biwiserglotel
0.
0.8
0.6
04-
02+
02
Figure 7. Average number of generations of the ENAS algorithms with population and crossover for solving the McC problem (M = 20, varying r). The ENAS algorithms include (A+AS-ENAS algorithm (with mutation only), (A+A)-ENAS algorithm with one-point crossover. and (ANA)-ENAS algorithm with uniform crossover, where À E (2, 4, 10).
19


Reviews:
[{"review_id": "4SzUaN7B9q", "reviewer": "Reviewer_eb31", "summary": "The paper delves into the runtime analysis of ENAS for multiclass classification，It introduces a new benchmark problem, MCC, designed to simulate multiclass classification tasks, and formulates a fitness function to evaluate neural architectures' performance on this problem. The authors also design a two-level search space, support detailed theoretical analysis. Empirical experiments further validate these theoretical results, highlighting the potential for simpler mutation strategies in ENAS design.\n\n## Update after rebuttal\n\nThe authors' rebuttal looks great to me. My final recommendation is a clear accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Many thanks for your recognition and encouraging comments of our work. Below, we take the opportunity to respond to your concerns.\n\n>1.The proposed MCC benchmark problem, while theoretically sound, is highly simplified and may not reflect the complexity of real-world multiclass classification tasks.\n\nThe MCC benchmark is designed to capture essential properties of real-world multiclass classification tasks, including both linearly and nonlinearly divisible decision regions (e.g., half-space region, unbounded/bounded polyhedra region). Many classification problems can be described as a disjoint union of these decision regions. While real-world tasks may involve additional complexities (e.g., noisy or more complex decision boundaries) that extend beyond the current MCC scope, the MCC benchmark provides a tractable yet representative framework for analyzing ENAS behaviors.  This simplified abstraction aligns with conventions in the theory community of evolutionary computation, where unimodal benchmark problems like OneMax and LeadingOnes similarly simplify real-world problems to analyze algorithmic behaviors (Droste et al., 2002; Doerr et al., 2008; Doerr & Goldberg, 2013; Witt, 2013). We will explicitly discuss the limitations of the MCC problem in the manuscript.\n\n>2.The runtime analysis focuses on the number of generations required to find an optimal solution but does not consider the computational resources (e.g., memory, processing power) needed to evaluate each candidate architecture.\n\nOur runtime analysis focuses on the expected number of fitness evaluations (i.e., the expected number of generations in this work) required to find an optimal solution, which concerns the ENAS search strategy and aligns with the theory community of evolutionary computation (Auger & Doerr, 2011; Neumann & Witt, 2010; Zhou et al., 2019; Doerr & Neumann, 2020). The computational cost (such as memory and processing power) per fitness evaluation is determined by the architecture training and validation process, which remains independent of the ENAS search strategy under analysis and consequently does not impact our runtime analysis. We will clarify this distinction in the manuscript.\n\n>3.The authors do not address how the proposed theoretical bounds scale with increasing problem complexity, which is crucial for understanding their practical feasibility.\n\nThe problem complexity is determined by two parameters: $M$ (the number of classes) and $r$ (which affects the decision regions for each class). As proven in Theorems 4.1 to 4.4, the expected runtime $\\mathbb{E}[T]$ of (1+1)-ENAS grows polynomially with $M$ and $r$. We will revise the manuscript to explicitly discuss this.\n\n>4.The analysis assumes a relatively uniform and idealized search space, methods like dropout, batch normalization, or architectural constraints are not accounted for. These techniques can significantly influence the optimization landscape and runtime behavior of ENAS algorithms. Whether these techniques affect the optimization and runtime behavior of ENAS algorithms.\n\nWe fully agree that techniques like dropout, batch normalization, and architectural constraints can affect the optimization and runtime behavior of ENAS algorithms. Specifically, dropout and batch normalization can introduce noise into the fitness evaluation result, thereby effecting the optimization and runtime behavior of ENAS algorithms. Additionally, architectural constraints can reshape the search space, thereby altering the fitness landscape and consequently impacting the optimization and runtime behavior of ENAS algorithms. Current frameworks exclude these components due to unresolved challenges: (1) nonlinear interactions between architectural fitness and the noise introduced by dropout and batch normalization, complicating fitness modeling; (2) architecture constraints (e.g., parameter/resource limits) will introduce multi-objective optimization (e.g., balancing accuracy and efficiency). We will discuss these aspects and outline future directions in the Conclusion.", "claims_and_evidence": "In general, the claims made in the submission are backed by a combination of rigorous mathematical proofs and experimental results.", "methods_and_evaluation_criteria": "The proposed methods and criteria are appropriate for the theoretical analysis.", "theoretical_claims": "I have checked the correctness of the proofs for the theoretical claims presented in the submission. As follows, Upper/Lower Bound on Expected Runtime for (1+1)-ENAS with One-bit/Bit-wise Mutation.", "experimental_designs_or_analyses": "Yes, I reviewed the experimental designs and analyses presented in the submission.  The experiments focus on evaluating the performance of the (1+1)-ENAS algorithm with different mutation strategies (one-bit and bit-wise mutations) on the proposed MCC benchmark problem.", "relation_to_broader_scientific_literature": "The paper makes several contributions that are well-aligned with the broader scientific literature.", "essential_references_not_discussed": "Yes, there are several related works that provide essential context for the key contributions of the paper.", "other_strengths_and_weaknesses": "**Pros as follows,**   \n1.The authors propose a multiclass classification benchmark problem (MCC) with a mathematically formulated fitness function. This is a significant contribution as it provides a standardized problem for analyzing ENAS algorithms.   \n2.The two-level search space (cells and blocks) is designed to be consistent with common ENAS settings, this design supports the theoretical analysis.   \n3.The theoretical results are supported by empirical studies, demonstrating the practical relevance of the findings.   \n\n**Cons as follows,**   \n1.The proposed MCC benchmark problem, while theoretically sound, is highly simplified and may not reflect the complexity of real-world multiclass classification tasks.   \n2.The runtime analysis focuses on the number of generations required to find an optimal solution but does not consider the computational resources (e.g., memory, processing power) needed to evaluate each candidate architecture.     \n3.The authors do not address how the proposed theoretical bounds scale with increasing problem complexity, which is crucial for understanding their practical feasibility.   \n4.The analysis assumes a relatively uniform and idealized search space, methods like dropout, batch normalization, or architectural constraints are not accounted for. These techniques can significantly influence the optimization landscape and runtime behavior of ENAS algorithms. Whether these techniques affect the optimization and runtime behavior of ENAS algorithms.", "other_comments_or_suggestions": "The manuscript makes nice contributions to the theoretical understanding of ENAS for multiclass classification. The work of theoretical analysis is difficult and admire the author's efforts in this direction. More comments refer to weaknesses.", "questions_for_authors": "Refer to weaknesses.", "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": "", "extra_scores": {}}, {"review_id": "bmEQga4oTK", "reviewer": "Reviewer_dy7r", "summary": "This paper investigates the runtime analysis of Evolutionary Neural Architecture Search for multiclass classification problems. The core of the research is the proposal of a multiclass classification benchmark problem and the design of a two-level search space based on this problem. The authors then analyze the expected runtime bounds of the (1+1) ENAS algorithm with one-bit and bit-wise mutations for solving MCC. The results show that both mutation strategies achieve similar performance in terms of expected runtime, which is further verified by empirical studies. This work represents the first theoretical analysis of ENAS for multiclass classification, providing new insights into understanding ENAS.\n\n## update after rebuttal\n\nAfter the rebuttal, I feel my concerns have been well-discussed by the authors, although some of weaknesses are not very easy to modify during a such short period. Therefore, I choose to keep my positive scores, and I believe that all the reviewers are lean towards to accept this submission.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Your detailed comments are much appreciated, and we will revise the manuscript accordingly. Below, we address your questions.\n\n>1.How does the proposed runtime analysis scale with increasing problem complexity (e.g., higher-dimensional input spaces or larger numbers of classes)? Are there any limitations in extending the analysis to more complex scenarios?\n\n(1) We first explain the impact of increasing problem complexity by using larger numbers of classes (i.e., increasing $M$ in the analysis). In this case, the proposed runtime analysis scale will not be changed. This can be found from our theoretical results (Theorems 4.1 to 4.4) that reveal the relationship between runtime $T$ and classes number $M$, i.e., the expected runtime $\\mathbb{E}[T]$ of (1+1)-ENAS grows polynomially with $M$. Next, we explain the impact of increasing problem complexity by using higher-dimensional input spaces. In this case, runtime analysis becomes more challenging due to that the fitness function is difficult to express in a mathematically tractable form. This difficulty arises from the fact that the mathematically formulated fitness function is derived by the hypervolume of the decision regions, while the higher-dimensional input spaces result in that the hypervolume of the higher-dimensional decision regions cannot be calculated from the geometric properties of the decision regions (i.e., higher-dimensional spaces make it difficult to provide a geometric interpretation of the neural network’s decision regions). \n(2) Yes, the main limitation is that the complex decision regions restrict the mathematical formulation of the fitness function. This, in turn, makes it difficult to directly assess the progress of the ENAS search process, which is a crucial step in the runtime analysis. We will revise to add more discussion. Thank you.\n\n>2.The fitness function assumes optimal parameter tuning for each architecture. How sensitive are the theoretical results to deviations from this assumption? Could the analysis be extended to account for suboptimal parameter tuning?\n\n(1) The theoretical results are robust to small deviations from optimal parameter tuning. Specifically, deviations from optimal parameter tuning will introduce noise into the fitness evaluation process, which could potentially alter the fitness landscape and disrupt the ranking of architectures' fitness values. However, if the fitness values maintain a high correlation with the true performance of the architectures, the impact on the ranking of candidate architectures is likely to be minimal, and thus unlikely to affect the search results in each round. In such cases, the theoretical results may not be notably affected. Overall, if the deviation is very small, the impact on the theoretical results is not significant. \n(2) To account for suboptimal tuning, the analysis could be extended via (1+$\\epsilon$)-approximation or noisy optimization frameworks. We will discuss these directions in the revised manuscript and pursue them in future work. We appreciate your support as we advance this work.\n\n>3.The paper shows that one-bit and bit-wise mutations achieve similar performance. How do these findings influence the design of future ENAS algorithms?\n\nThe design complexity of one-bit and bit-wise mutation–based ENAS algorithms differs: one-bit mutation is a simple and parameter-free operator that applies a single random change per step, while bit-wise mutation requires to tune the bit-flip probability (e.g., setting $p=1/n$ versus $p=0.5$ yields vastly different exploration-exploitation balances, where $n$ is the problem size). Our findings show that the simpler one-bit mutation can be prioritized in ENAS algorithm design. This is particularly effective for block/cell-based search spaces, where one-bit mutation operator could achieve significant changes in neural architecture. Furthermore, this aligns with practical ENAS methods like AE-CNN (Sun et al., 2019b), which utilize single-step mutation (functionally analogous to one-bit mutation) as their core search operator. We thank the reviewer for this comment and will revise to strengthen the discussion on mutation operator selection.\n\n>4.Can the theoretical framework be extended to analyze more complex ENAS algorithms? If so, what are the key challenges?\n\nYes, the theoretical framework—including search space partitioning, optimization phase division, distance function definition, and individual transition probability analysis—can be extended to more complex ENAS algorithms. However, this extension faces key challenges: 1) how to calculate the probability of ENAS algorithm making progress in one step; 2) how to derive a tighter expectation of one-step progress (which is related with the progress derived by evolution operators); 3) how to select an appropriate runtime analysis tool based on the relationship between the distance at each generation (iteration) and the expected progress.", "claims_and_evidence": "The claims made in the submission are generally supported by clear and convincing evidence, particularly in the context of the theoretical analysis and the proposed benchmark problem.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria in this paper are well-aligned with the problem of runtime analysis for evolutionary neural architecture search in multiclass classification.", "theoretical_claims": "The proofs presented in the paper are logically structured and follow established techniques in runtime analysis. Further validation through sensitivity analysis, empirical studies, and exploration of alternative proof techniques would strengthen the theoretical claims and enhance their practical applicability.", "experimental_designs_or_analyses": "Yes, I reviewed the soundness and validity of the experimental design and analysis presented in the paper, focusing on the empirical evaluation of the (1+1)-ENAS algorithm with different mutation strategies on the proposed MCC problem.", "relation_to_broader_scientific_literature": "The key contributions of this paper are related to several important areas of the broader scientific literature, particularly in the fields of Evolutionary Computation, Neural Architecture Search, and Runtime Analysis of Evolutionary Algorithms.", "essential_references_not_discussed": "There is no essential references missing.", "other_strengths_and_weaknesses": "**Strengths,**   \n- This paper is the first to conduct a runtime analysis of ENAS for multiclass classification problems. By proposing the MCC problem and a mathematically formulated fitness function, it provides a benchmark for theoretical research on ENAS.   \n- The authors use rigorous mathematical tools, such as multiplicative drift analysis and fitness-level techniques, to derive upper and lower bounds on the expected runtime.   \n- The findings suggest that simpler mutation strategies like one-bit mutation can be effective in ENAS, which may simplify the design of future ENAS algorithms.   \n\n**Weaknesses,**   \n- How does the proposed runtime analysis scale with increasing problem complexity (e.g., higher-dimensional input spaces or larger numbers of classes)?  Are there any limitations in extending the analysis to more complex scenarios?   \n- The fitness function assumes optimal parameter tuning for each architecture. How sensitive are the theoretical results to deviations from this assumption?  Could the analysis be extended to account for suboptimal parameter tuning?   \n- The paper shows that one-bit and bit-wise mutations achieve similar performance. How do these findings influence the design of future ENAS algorithms?   \n- Can the theoretical framework be extended to analyze more complex ENAS algorithms? If so, what are the key challenges?", "other_comments_or_suggestions": "Overall, the manuscript is technically sound and well-presented, with some theoretical insights. Please refer to other strengths and weaknesses for drawbacks.", "questions_for_authors": "Please refer to my weaknesses listed above.", "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": "", "extra_scores": {}}, {"review_id": "uCXmZ2Iaxg", "reviewer": "Reviewer_iu6X", "summary": "This paper introduces a novel runtime analysis framework for evolutionary neural architecture search (ENAS). Compared with the previous studies, which focus on the binary classification problem, the runtime analysis focuses on the multiclass classification problem in this work. Specifically, this study first introduces a multiclass classification benchmark problem called MCC. Then, a more practical search space with two interrelated levels is designed. Based on this, the expected runtime bounds of (1+1)-ENAS are analyzed. ## update after rebuttal", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Many thanks for your recognition and comments of our work. Below, we would like to take this opportunity to address your concerns.\n\n>1. The authors state that the expected runtime to find the target solution is $O(rM\\ln(rM))$. However, it is suggested to discuss how this conclusion contributes to ENAS.\n\nThis result highlights the relationship between the expected runtime and key problem parameters, i.e., $M$ (the number of classes) and $r$ (which affects the decision regions for each class). The result provides two insights for ENAS: 1) due to the polynomial runtime dependency on classification problem parameters $M$ and $r$, the ENAS generations (iterations) should scale with classification difficulty; 2) since our runtime results (Theorems 4.1 to 4.4) show that one-bit and bit-wise mutation achieve comparable runtime in (1+1)-ENAS solving MCC problem, the one-bit mutation as a simpler and parameter-free operator (e.g., no need to tune bit-flip probability) can be prioritized in ENAS design.\n\n>2. I wonder if the theoretical findings are valid when there are infinite classes. Please provide more details regarding this point.\n\nYes. As shown in Theorems 4.1 to 4.4, the expected runtime $\\mathbb{E}[T]$ holds with any number $M$ of classes. This finding shows that the architecture search difficulty increases with $M$ due to the finer partitioning of the decision spaces. Moreover, the theoretical framework does not impose any upper limit on the number $M$ of classes, meaning the findings apply regardless of whether $M$ is finite or tends to infinity. However, in extreme cases where $M$ becomes infinitely large, practical considerations such as finite computational resources should be taken into account.\n\n>3. Is there a sequence for the two types of mutations in the two-level mutation process? How does this sequence affect the theoretical analysis in this work?\n\nYes, there is a sequence in the two-level mutation process. By first selecting the cell to mutate (outer-level mutation) and then applying the mutation (inner-level mutation) to the selected cell, we can track the expected changes between the parent and offspring, and also can quantify the progress made at each step. However, reversing the sequence would make the algorithm infeasible, as the index of the cell to be mutated would be unknown, making it unclear where the inner-level mutation should be applied. Specifically, given a solution $\\pmb{x}$, which is encoded by $M-1$ triplets of integers, i.e., $\\pmb{x} =${$(n_A^1, n_B^1, n_C^1),\\ldots,(n_A^{M-1}, n_B^{M-1}, n_C^{M-1})$},  the algorithm must first select the cell index $m\\in${$1,\\ldots,M-1$}, and then apply the inner-level mutation to modify the selected cell $(n_A^m,n_B^m,n_C^m)$.\n\n>4. In lines 223-229 of page 5, the authors state that the definition of classification accuracy is suitable for balanced datasets. I wonder if the distribution of data is imbalanced (e.g., long-tailed data), what impact will it have on the theoretical findings?\n\nIf the data distribution is imbalanced, the formulation of the fitness function (i.e., Eq. (2)) will need to consider the distribution of each class of data, which will introduce new conditions for judging whether each cell reaches the optimal state or not in the ENAS search process, e.g., the conditions $I_{\\pmb{x}}^m=2r$ and $J_{\\pmb{x}}^m=2r$ for $o^m$ to be 1 (as stated in line 353) will be affected by the distribution of data. Furthermore, a dependency would exist between the number of optimal cells $|\\pmb{o}|_1$ in Eq. (3) and the distribution of data. Consequently, this affects the computation of expected progress (e.g., Eq. (4)) and the distribution of the optimal cells in the initial solution (e.g., Eq. (6)), ultimately making the theoretical findings (i.e., expected runtime shown in Theorems 4.1– 4.4) dependent on the data distribution.", "claims_and_evidence": "All the claims made in this work are well supported by theoretical proofs or experimental results, none of which is problematic.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria indeed make sense for the problem in this work. The multiclass classification benchmark problem successfully extends the runtime analysis from binary classification to multiclass classification.", "theoretical_claims": "I have checked the correctness of all proofs and theoretical claims, and believe that they are all correct.", "experimental_designs_or_analyses": "I have checked the experimental results regarding the different mutation settings in (1+1)-ENAS algorithm. This set of results can well support the claims made in Theorems 4.1 to 4.4.", "relation_to_broader_scientific_literature": "In terms of the runtime analysis for ENAS, previous studies mainly focus on the binary classification problem, and their representation of the search space limits the application to multiclass classification problem. Different from these studies, this work achieves the analysis for multiclass problem via the proposed multiclass classification benchmark problem and the search space with two inter-related levels.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n+ This paper mainly focuses on the runtime analysis of ENAS, which is a very important topic in NAS research. The authors provided several novel viewpoints in this field.\n+ This paper pushes the runtime analysis of ENAS toward the new area regarding the multiclass classification problem. Compared with the previous studies focusing on the binary classification problem, this work achieves significant improvements upon them.\n+ A multiclass classification benchmark problem and a novel fitness function are introduced. The fitness function not only contributes to the theoretical analysis of ENAS, but also can be transferred to other fields in evolutionary computation.\n+ The authors present a practical search space specifically for the multiclass classification problem, pushing the search space design towards a new direction in the field of ENAS.\n+ All the claims in this work are well supported by sufficient theoretical proofs or experimental results.\n+ The expected runtime bounds obtained contribute to the design of ENAS algorithms, especially for the design of the mutation operator.\n+ The paper is very well presented, and the illustrations and visualizations are nicely done.\n\nWeaknesses:\n+ The authors state that the expected runtime to find the target solution is $O(rMln(rM))$. However, it is suggested to discuss how this conclusion contributes to ENAS. \n+ I wonder if the theoretical findings are valid when there are infinite classes. Please provide more details regarding this point.\n+ Is there a sequence for the two types of mutations in the two-level mutation process? How does this sequence affect the theoretical analysis in this work?\n+ In lines 223-229 of page 5, the authors state that the definition of classification accuracy is suitable for balanced datasets. I wonder if the distribution of data is imbalanced (e.g., long-tailed data), what impact will it have on the theoretical findings?", "other_comments_or_suggestions": "None.", "questions_for_authors": "Please refer to the Other Strengths And Weaknesses section.", "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": "", "extra_scores": {}}, {"review_id": "awz5cRZLBM", "reviewer": "Reviewer_26fJ", "summary": "This study presents a theoretical analysis of the runtime of the ENAS algorithm in solving multiclass classification problems. The authors first introduce a benchmark problem and then propose a two-level search space. Based on this design, the authors analyze the upper and lower bounds on the expected runtime and provide empirical results that validate their theoretical findings. The findings indicate that the simple one-bit mutation can achieve similar performance to the commonly used bit-wise mutation of ENAS.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Many thanks for your valuable comments of our work. Below, we would like to take this opportunity to respond to your concerns.\n\n>1. Are the ENAS algorithms widely used in practice are (1+1)-ENAS? In other words, can this finding well support the widely used ENAS algorithms in practice?\n\n(1) In practice, most ENAS algorithms are population-based, while (1+1)-ENAS serves as a theoretical foundation for runtime analysis and designing population-based algorithms. (2) Yes. Our finding shows that simple one-bit mutation achieves comparable runtime performance to bit-wise mutation on the MCC problem, validating that the one-bit mutation is not inherently inefficient. This aligns with practical ENAS methods like AmoebaNet (Real et al., 2019) and AE-CNN (Sun et al., 2019b), which utilize single-step mutation (functionally analogous to one-bit mutation) as their core search operator. Thanks to your comment, we will revise to discuss the connection to practical implementation.\n\n>2.The differences and the challenges of the multiclass classification and binary classification for ENAS algorithms should be well-defined.\n\nDifferences: 1) **decision regions**: multiclass classification divides input space into $M$ decision regions (vs. two in binary classification), increasing neural architectural demands; 2) **classification accuracy**: multiclass classification aggregates per-class accuracy across all $M$ regions, amplifying the complexity of the fitness evaluation; 3) **search space**: the neural architecture for solving multiclass classification is a combination of multiple binary classifiers or a more complex architecture (vs. binary classification’s binary classifier), exponentially expanding the search space. \nChallenges: 1) **problem definition**: accurately modeling inter-class dependencies and region-specific sample distributions; 2) **fitness function**: mathematically formulating the fitness (i.e., classification accuracy) of neural architecture from geometric properties; 3) **search space partition**: partitioning the search space by analyzing the interactions between architectural components (e.g., blocks, cells). \nThanks to your suggestion, we will incorporate these clarifications into the revised manuscript.\n\n>3. Do the authors believe that all the bit-wise mutations in ENAS should be replaced with one-bit mutation?\n\nNo. Consistent with the No Free Lunch Theorem, neither operator is universally optimal: bit-wise mutation excels in exploration-heavy scenarios (e.g., topology-based search spaces), while one-bit mutation prioritizes simplicity and serves as a parameter-free alternative (e.g., no need to tune bit-flip probability). As an initial attempt at ENAS runtime analysis, we prioritize foundational cases, while future work will expand comparisons to diverse tasks. We appreciate your support as we advance this work.\n\n>4.This study focuses only on mutation, ignoring other important evolutionary operators, which should be noted as a limitation.\n\nOur study focuses on mutation as it is a core component of ENAS and many ENAS are limited to mutation only (Real et al., 2017; Real et al., 2019; So et al., 2021). This also aligns with the theory community of evolutionary computation, where initial analyses often start with mutation (Auger & Doerr, 2011; Neumann & Witt, 2010; Zhou et al., 2019; Doerr & Neumann, 2020), thereby providing a stepping stone for further exploration. While advanced operators like crossover and stochastic selection are vital in practice, their runtime analysis remains challenging due to irregular combinatorial interactions and limited theoretical frameworks. We will explicitly discuss this.\n\n>5.The experiments of this study are limited in scope. Including more datasets or SOTA ENAS algorithm could strengthen the findings.\n\nOur search space is simplified for the MCC problem, which makes it difficult to directly apply the studied ENAS framework to other domains (e.g., image classification) without architectural re-engineering. Future work will expand this framework to diverse tasks. In addition, to further strengthen our finding, we have extended experiments to three SOTA ENAS algorithms: ($\\lambda$+$\\lambda$)-ENAS with mutation only ($\\lambda\\in\\{2,4,10\\}$), which is adopted in methods like LEIC (Real et al., 2017) and AmoebaNet (Real et al., 2019); one-point crossover-based ENAS, which is adopted in CNN-GA (Sun et al., 2019a) and ENAS-kT (Yang et al., 2023); and uniform crossover-based ENAS, which is adopted in Genetic CNN (Xie & Yuille, 2017). All additional experiments are under identical problem settings (Section 5). The results (see anonymous links: [fixed $r=10$, varing $M$](https://anonymous.4open.science/r/5666/rebuttalFigs/a-varing-M.pdf) and [Fixed $M = 20$, varying $r$](https://anonymous.4open.science/r/5666/rebuttalFigs/b-varing-r.pdf)) show that one-bit mutation still performs better. Thanks to your suggestion, we will integrate them into the manuscript.", "claims_and_evidence": "All the claims of this study are well supported.", "methods_and_evaluation_criteria": "Both the introduced benchmark problem and the two-level search space can well support the ENAS problem at hand.", "theoretical_claims": "I have checked the correctness of the proofs for theoretical claims in this work, including the fitness function, the upper bound, and the lower bound, which are well designed and proofed.", "experimental_designs_or_analyses": "The experiments can justify the claims of this study, but more datasets should be better.", "relation_to_broader_scientific_literature": "The paper contributes to the theoretical understanding of ENAS by analyzing runtime bounds, which can be regarded as a continual work of Lv et al. This work extended the study from binary classification tasks to multclass classification tasks.\n\nLv Z, Bian C, Qian C, et al. Runtime Analysis of Population-based Evolutionary Neural Architecture Search for a Binary Classification Problem[C]//Proceedings of the Genetic and Evolutionary Computation Conference. 2024: 358-366.", "essential_references_not_discussed": "This study focuses on the runtime analysis of the ENAS algorithm, and the introduction and related works have discussed the more relevant aspects of the topic.", "other_strengths_and_weaknesses": "Strengths\n1. The paper provides the important theoretical findings of ENAS. The findings are crucial, especially for the multiclass optimization task for ENAS.\n2. The insights of the mutation operations can guide the design of the ENAS algorithms and also can simplify the existing ENAS algorithms.\n3. The upper and lower bounds for the runtime of ENAS, which can effectively guide the mutation selection of the ENAS algorithm.\n4. The definition of the MCC benchmark problem and the fitness function are good to support the following theoretical proof.\n5. The two-level search space aligns well with the application of ENAS algorithms in practice, making the theoretical findings applicable to real-world ENAS settings.\n6. All the theorems of the paper, such as runtime bounds and fitness function, are proved correctly.\n7. The empirical analysis is designed to verify the effectiveness of the theoretical findings.\n8. The paper is well-organized and the presentation is easy to understand.\n\nWeaknesses\n1. This study analyzes the (1+1)-ENAS algorithm and finds that simple one-bit mutation can achieve similar performance as commonly used bit-wise mutation. However, are the ENAS algorithms widely used in practice are (1+1)-ENAS? In other words, can this finding well support the widely used ENAS algorithms in practice?\n2. The differences and the challenges of the multiclass classification and binary classification for ENAS algorithms should be well-defined. Based on this definition, the contribution of this study can be more meaningful.\n3. Although the authors justify that one-bit mutation can be a powerful mutation operation for ENAS, they do not provide strong practical guidelines on how practitioners should choose between one-bit and bit-wise mutations in different settings. Do the authors believe that all the bit-wise mutations in ENAS should be replaced with one-bit mutation?", "other_comments_or_suggestions": "Here are some minor weaknesses of this study:\n1. This study focuses only on the mutation operations of the ENAS algorithm, ignoring other important evolutionary operators, e.g., crossover and selection operations, which are commonly used in practical ENAS implementations. The authors should discuss them in the limitation section.\n2. The experiments of this study are limited in scope. Including more datasets or SOTA ENAS algorithm could strengthen the findings.", "questions_for_authors": "Please check Other Strengths And Weaknesses and Other Comments Or Suggestion.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a theoretical runtime analysis of Evolutionary Neural Architecture Search (ENAS), specifically focusing on multiclass classification problems using a simple (1+1)-ENAS algorithm. The authors introduce a novel benchmark problem (MCC) designed for multiclass classification and a corresponding two-level search space representation. They derive theoretical upper and lower bounds (O(k^2 * n log n) and Ω(k^2 * n) respectively) on the expected runtime for (1+1)-ENAS using both one-bit and bit-wise mutation operators to find an optimal architecture within this framework. A key finding is that the simpler one-bit mutation achieves comparable theoretical performance to the more complex bit-wise mutation, a result supported by empirical validation. This work represents a significant step forward in the theoretical understanding of ENAS, extending prior analyses from binary to the more general multiclass setting.


The reviewers unanimously lean towards acceptance, with three recommending Accept (eb31, iu6X, 26fJ - with eb31 upgrading to Clear Accept post-rebuttal) and one recommending Weak Accept (dy7r). There is strong consensus on the paper's primary strengths. 
The authors provided comprehensive and thoughtful rebuttals that effectively addressed most reviewer concerns.
All reviewers acknowledged the rebuttals, and they appeared largely satisfied with the responses, leading one reviewer to upgrade their score and others to maintain positive recommendations while acknowledging the remaining (mostly inherent theoretical) limitations.

This paper makes a solid and novel contribution to the theoretical understanding of ENAS. Establishing the first runtime analysis for the multiclass setting is a significant achievement. The proposed benchmark and search space provide a foundation for future theoretical work in this area. The finding regarding the effectiveness of simple one-bit mutation, supported by both theory and empirical results (including the additional ones in the rebuttal), offers a valuable insight that could potentially simplify ENAS design.

While the work operates within a necessarily simplified theoretical framework (a common characteristic of rigorous runtime analysis), the authors have convincingly argued for its relevance and have diligently addressed the reviewers' concerns regarding scope and assumptions. The strong consensus among reviewers, particularly after the clarifying rebuttals and additional experiments, supports acceptance. This work is a valuable addition to the ICML proceedings, pushing the boundary of theoretical understanding in an important area of automated machine learning.
Decision: Accept (poster)