Runtime Analysis of Evolutionary NAS for Multiclass Classification

Many thanks for your valuable comments of our work. Below, we would like to take this opportunity to respond to your concerns.

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?

(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.

2.The differences and the challenges of the multiclass classification and binary classification for ENAS algorithms should be well-defined.

Differences: 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. Challenges: 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). Thanks to your suggestion, we will incorporate these clarifications into the revised manuscript.

3. Do the authors believe that all the bit-wise mutations in ENAS should be replaced with one-bit mutation?

No. 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.

4.This study focuses only on mutation, ignoring other important evolutionary operators, which should be noted as a limitation.

Our 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.

5.The experiments of this study are limited in scope. Including more datasets or SOTA ENAS algorithm could strengthen the findings.

Our 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$ and Fixed $M = 20$, varying $r$) show that one-bit mutation still performs better. Thanks to your suggestion, we will integrate them into the manuscript.

Many thanks for your recognition and comments of our work. Below, we would like to take this opportunity to address your concerns.

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.

This 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.

2. I wonder if the theoretical findings are valid when there are infinite classes. Please provide more details regarding this point.

Yes. 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.

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?

Yes, 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)$.

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?

If 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.

Many thanks for your recognition and encouraging comments of our work. Below, we take the opportunity to respond to your concerns.

1.The proposed MCC benchmark problem, while theoretically sound, is highly simplified and may not reflect the complexity of real-world multiclass classification tasks.

The 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.

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.

Our 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.

3.The authors do not address how the proposed theoretical bounds scale with increasing problem complexity, which is crucial for understanding their practical feasibility.

The 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.

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.

We 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.

Your detailed comments are much appreciated, and we will revise the manuscript accordingly. Below, we address your questions.

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?

(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). (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.

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?

(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. (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.

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?

The 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.

4.Can the theoretical framework be extended to analyze more complex ENAS algorithms? If so, what are the key challenges?

Yes, 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.