- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This manuscript presents a runtime analysis for a crossover-based evolutionary neural architecture search (ENAS) algorithm. The analysis is performed on one specific architecture designed for multi-class classification problems. The results show that crossover does not significantly improve the optimization efficiency compared to mutation-only variant, but a better preservation of population diversity could improve the efficiency of crossover. A complementary empirical study is performed to validate the theoretical results.
Critical strengths
A rigorous theoretical analysis is always helpful for the evolutionary computation community. The theoretical result forms a good foundation for further algorithmic developments.
Critical weaknesses
- The theoretical analysis is limited to one specific architecture and one task. The generalizability of the theoretical conclusion is doubtful, limiting its impact on broader understanding of the role of crossover in ENAS.
- There is no theoretical or empirical comparison between the duplicate-based tie-breaking crossover and mutation. It would be interesting to see whether additional diversity-preservation mechanism could make crossover outperform mutation.
Questions for authors
- Do you think the theoretical analysis could be easily extend to other architectures or task types? More discussions on this aspect would be helpful.
- How is the performance of the duplicate-based tie-breaking crossover compared with the mutation? Could you add some theoretical and empirical analysis about this missing comparison?
- The literature review is missing some relevant works that also performs a theoretical analysis of crossover operator in ENAS setup, e.g., the SEP crossover work [1]. Could you discuss the connections to that work?
[1] “Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search”, ICML 2023.
3 comments
Thanks for the detailed responses. I will increase my rating from 2 to 3.
Dear Reviewer 9vGW,
Thanks for your positive feedback! We sincerely appreciate your time and constructive comments, which have helped us improve the paper.
Best regards,
The Authors
We thank the reviewer for the constructive suggestions and for recognizing the value of theoretical analysis for evolutionary computation. Following your comments, we have strengthened the comparison with mutation-only search and clarified the relationship to prior work.
Extension to other architectures and task types.
Thank you for suggesting a discussion of extensions beyond MCC. To our knowledge, rigorous runtime analyses of ENAS have so far focused on two classification benchmarks, UNIFORM and MCC (Lv et al., 2024, 2025). UNIFORM has three integer-valued block counts. MCC has M−1 recombinable cells with explicit fitness contributions, enabling study of crossover over growing numbers of components. Extensions require architecture- and task-specific progress measures and transition bounds across evolving populations.
Section 5 (Table 2) adds NAS-Bench-201 (Dong & Yang, 2020), which is a popular benchmark used in NASWOT (Mellor et al., 2021), DrNAS (Chen et al., 2021) and AZ-NAS (Lee & Ham, 2024), tabulating networks trained on CIFAR-10, CIFAR-100 and ImageNet16-120, and covering evolutionary, differentiable and training-free approaches. Further benchmarks and architecture spaces are future directions.
Duplicate-based crossover compared with mutation-only search.
We added mutation-only ENAS with the same duplicate-based tie-breaking, its runtime analysis, and direct comparisons.
Theorem 4 and proof sketch. For μ parents, λ offspring and pm=c/(M−1)<1 with constant c>0, Theorem 4 gives
\mathbb{E}[T]=O\left(\mu+rM\max\left\\{\lambda,\frac{\mu e^c}{c}\ln(rM)\right\\}\right),
matching Theorem 2 for uniform tie-breaking. We maximize I, then J−ϵ subject to I=N=2r(M−1). At deficit d, a best parent is chosen with probability at least 1/μ and has at least d/(2r) deficient cells. Improving one while preserving the others gives qd=Ω(cd/(μecrM)). Duplicate-based tie-breaking preserves elitism. The evaluation cost per level is O(maxλ,μecrM/(cd)). Summing both phases and adding initialization proves the bound (Appendix A.2.6).
MCC comparison. We use r=10,c=1,μ=λ=4,pm=1/(M−1), 30 independent runs and a 107-fitness-evaluation (FE) budget. C uses uniform crossover then mutation (pc=1/2), and NC uses mutation only (pc=0). Uni/Dup denote uniform/duplicate-based fitness tie-breaking. FEs include initialization and repeats. All runs succeed. Entries are mean FEs in thousands (Section 5, Table 1):
Holding Dup fixed, crossover reduces mean FEs by 13.0% at M=100.
NAS-Bench-201 comparison. We use μ=λ=100, 50 paired runs per method and dataset, and a 2,000-FE budget. Fitness is the mean 200-epoch validation accuracy over available training repeats. Initialization is uniform with replacement. Each of six entries, with five operation choices, mutates independently with probability 1/6 to another choice. C uses entry-wise uniform crossover with pc=1/2. Dup identifies identical six-operation encodings. Evaluations to the maximum tabulated fitness, accepting tied optima, are capped at 2,000.
Dup+C reduces mean capped FEs versus Uni+NC by 24.47%, 31.85% and 18.73% on the three datasets, all significant after Holm correction. Reductions versus Dup+NC are significant on CIFAR-10 and CIFAR-100 (Section 5, Table 2, Appendix B.4).
Connection to shortest edit path crossover.
Thank you for this interesting reference. Qiu & Miikkulainen (2023) address graph-encoding permutations via shortest edit path crossover and analyze expected offspring improvement in graph-edit distance to an optimum. We added it to the Introduction. Total runtime requires controlling dependent population updates: selection changes available parents and may remove complementary components. Our analysis bounds progress and waiting times across intermediate states, including revisits and diversity loss, complementing their offspring-level analysis.
References cited in this response:
We hope our response has addressed your concerns. If we have missed anything, please let us know.