acceptodds
Under review as a conference paper at ICLR 2027

Runtime Analysis of Crossover-based Evolutionary Neural Architecture Search for Multiclass Classification Problems

Abstract

Crossover-based evolutionary algorithms (EAs), which generate offspring through recombination and mutation, have been widely applied to neural architecture search for automated design of deep neural architectures. However, it remains unclear whether and when the crossover operator benefits the evolutionary neural architecture search (ENAS) algorithm. To bridge this gap, this work analyzes its role by conducting runtime analysis, which is an essential theoretical aspect of EAs for understanding whether evolutionary operators can accelerate the search for optimal or approximate solutions and under which conditions such acceleration occurs. Specifically, we first develop a runtime analysis framework that captures both progress and potential regress occurring in each generation. Based on this, we analyze the runtime of the ENAS algorithm with crossover on multiclass classification problems, and the results reveal that crossover may not always accelerate ENAS, particularly when it is frequently applied to similar or identical individuals. Motivated by the observation, we further introduce a diversity-preserving mechanism through a duplicate-based tie-breaking rule into the ENAS algorithm with crossover to prevent similar or identical individuals from surviving to the next generation, and analyze its effect on the expected runtime. Our results show that maintaining population diversity may improve the efficiency of crossover. We hope this work may provide theoretical support to deepen the understanding of crossover in ENAS and offer insights into designing effective ENAS algorithms.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Evolutionary neural architecture search(ENAS), Evolutionary machine learning, Evolutionary algorithm (EA), Runtime analysis

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_9vGWOpenReview ↗
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
  1. 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.
  2. 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
  1. Do you think the theoretical analysis could be easily extend to other architectures or task types? More discussions on this aspect would be helpful.
  2. 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?
  3. 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
AuthorsOpenReview ↗

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.

  1. 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−1M-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.

  2. 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 μ\mu parents, λ\lambda offspring and pm=c/(M−1)<1p_m=c/(M-1) < 1 with constant c>0c > 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 II, then J−ϵJ-\epsilon subject to I=N=2r(M−1)I=N=2r(M-1). At deficit dd, a best parent is chosen with probability at least 1/μ1/\mu and has at least d/(2r)d/(2r) deficient cells. Improving one while preserving the others gives qd=Ω(cd/(μecrM))q_d=\Omega(cd/(\mu e^c rM)). Duplicate-based tie-breaking preserves elitism. The evaluation cost per level is O(max⁡λ,μecrM/(cd))O(\max\\{\lambda,\mu e^c rM/(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)r=10,c=1,\mu=\lambda=4,p_m=1/(M-1), 30 independent runs and a 10710^7-fitness-evaluation (FE) budget. C uses uniform crossover then mutation (pc=1/2p_c=1/2), and NC uses mutation only (pc=0p_c=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):

    MMUni+NCDup+NCUni+CDup+C
    246.346.215.745.64
    5014.4114.2513.0212.74
    10030.7631.1828.7027.13

    Holding Dup fixed, crossover reduces mean FEs by 13.0% at M=100M=100.

    NAS-Bench-201 comparison. We use μ=λ=100\mu=\lambda=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/61/6 to another choice. C uses entry-wise uniform crossover with pc=1/2p_c=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).

  3. 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:

  • Chen et al. DrNAS: Dirichlet Neural Architecture Search. ICLR, 2021.
  • Dong & Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search. ICLR, 2020.
  • Lee & Ham. AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search. CVPR, 2024.
  • Lv et al. Runtime analysis of population-based evolutionary neural architecture search for a binary classification problem. GECCO, 2024.
  • Lv et al. Runtime Analysis of Evolutionary NAS for Multiclass Classification. ICML, 2025.
  • Mellor et al. Neural Architecture Search without Training. ICML, 2021.
  • Qiu & Miikkulainen. Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search. ICML, 2023.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

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

Reviewer_xD4AOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the runtime efficiency of evolutionary neural architecture search, focusing on whether crossover provides a meaningful optimization advantage over mutation alone. The results suggest that crossover does not necessarily improve runtime under standard selection, while preserving population diversity through a modified tie-breaking strategy may lead to better performance on the studied multiclass classification benchmark. The paper offers a useful perspective on the relationship between population diversity and evolutionary search efficiency. However, the theoretical results do not conclusively establish the runtime advantage of crossover, and the evidence is limited to a specific benchmark. Overall, the work presents an interesting theoretical investigation, but its claims about the benefits and broader applicability of the proposed approach remain insufficiently substantiated.

Critical strengths

1.The paper addresses a relevant and insufficiently understood theoretical question. Although crossover is widely used in evolutionary neural architecture search, its runtime benefits are not guaranteed. Investigating when crossover helps and how population diversity affects its effectiveness is a meaningful problem in evolutionary computation.

2.The proposed analysis framework explicitly accounts for both progress and regress. By decomposing the optimization process into phases and distinguishing population states according to their fitness levels and cell-wise contributions, the authors provide a structured approach to analyzing the interaction between crossover, mutation, and environmental selection.

3.The paper connects theoretical analysis with an actionable algorithmic modification. Rather than stopping at the observation that crossover may be ineffective, the authors introduce a duplicate-based tie-breaking rule intended to preserve population diversity. This provides a concrete mechanism that can be evaluated both theoretically and empirically.

4.The experimental comparisons are relevant to the paper's central claims. The experiments compare crossover and mutation-only variants, different tie-breaking rules, population configurations, and mutation strengths. The reported results are broadly consistent with the authors' argument that preserving diversity can improve crossover effectiveness on the studied benchmark.

Critical weaknesses

1.Limited theoretical conclusions. The derived upper bounds do not conclusively establish that crossover improves expected runtime over mutation-only search.

2.Limited generalizability. The analysis is tailored to a specific geometric MCC benchmark, making its applicability to more general neural architecture search problems uncertain.

3.Limited experimental coverage. The evaluation considers only one benchmark and a small set of population configurations, leaving the robustness of the findings insufficiently

Questions for authors
  1. Can the authors provide a more precise interpretation of what these bounds establish, and whether any conditions are known under which crossover can be rigorously shown to improve expected runtime? The authors need clarify the strength of the theoretical conclusions regarding the benefit of crossover.

2.How sensitive is the proposed duplicate-based tie-breaking rule to the definition of an outer encoding?

3.Can the authors provide additional evidence for the robustness of the proposed mechanism? In particular, how does its performance change with larger population sizes, different crossover probabilities, and different mutation strengths.

2 comments
AuthorsOpenReview ↗

We thank the reviewer for the constructive comments and for recognizing the value of our analysis of crossover and population diversity. Following your suggestions, we have clarified the theoretical claims and expanded the experimental study, as detailed below.

  1. What the runtime bounds establish.

    Theorem 1 shows how crossover exploits different cell-wise II-vectors and how selection can remove them, causing the fallback i.3→i.2i.3\to i.2. Lemma 2 prevents this fallback while the best fitness is unchanged. Removing the fallback term yields a smaller Dup upper bound within this analysis when rM/μ>ln⁡μln⁡(rM)rM/\mu > \ln\mu\ln(rM).

    We have also added a bound using the branch without crossover: $ \mathbb E[T] =O\!\left(\mu+rM\max\left\{ \lambda,\frac{\mu e^c}{c}\ln(rM)\right\}\right). $ At distance dd in either optimization phase, an improving mutation has probability Ω(cd/(μecrM))\Omega(cd/(\mu e^c rM)) per offspring. Skipping crossover preserves this event with a factor of 1/21/2. Bounding the waiting time over λ\lambda offspring and summing the distance levels gives the displayed guarantee. Section 3.2 and Appendix A.2.3 present this argument, alongside the case-based explanation of crossover and diversity.

  2. Scope of the analysis and evidence 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, limiting the study of crossover over a growing number of components. MCC has M−1M-1 recombinable cells, each with three block counts, enabling analysis of complementary contributions and their preservation.

    Following your suggestion to examine performance beyond MCC, we have added experiments on NAS-Bench-201 (Dong & Yang, 2020). This widely used benchmark has been adopted in NASWOT (ICML) (Mellor et al., 2021), DrNAS (ICLR) (Chen et al., 2021) and AZ-NAS (CVPR) (Lee & Ham, 2024). It provides tabulated results from networks trained on real image classification datasets.

    Settings and metrics. On CIFAR-10, CIFAR-100 and ImageNet16-120, we use μ=λ=100\mu=\lambda=100, 50 paired runs per method and dataset, and a 2,000-fitness-evaluation (FE) budget. Fitness is the mean 200-epoch validation accuracy over available repeats. Six entries with five operation choices mutate independently with probability 1/61/6, uniformly to another choice. C uses entry-wise uniform crossover then mutation (pc=1/2p_c=1/2), and NC uses mutation only (pc=0p_c=0). Uni/Dup denote uniform/duplicate-based fitness tie-breaking. Duplicates have identical six-entry encodings. Initialization is uniform with replacement. FEs include initialization and repeats, counting to any tabulated optimum and capped at 2,000.

    Mean capped FEsCIFAR-10CIFAR-100ImageNet16-120
    Uni+NC1076.61123.21564.7
    Uni+C883.1768.41289.2
    Dup+NC1087.41100.11492.8
    Dup+C813.2765.41271.6

    Dup+C reduces mean capped FEs versus Uni+NC by 24.47%, 31.85% and 18.73%, all significant after Holm correction. Reductions versus Dup+NC are significant on CIFAR-10 and CIFAR-100. Appendix B.4 gives additional settings.

  3. Sensitivity to the outer encoding.

    Thank you. We compare Uni, Dup-Raw (identical block-count encodings) and Dup-Outer (identical ordered cell-contribution pairs (Im,Jm)(I^m,J^m)), fixing all other components. At r=10,c=1,pc=1/2r=10,c=1,p_c=1/2, M=24,100M=24,100 and μ=λ=4,20\mu=\lambda=4,20, we use 1,000 independent successful runs per method and setting. Dup-Outer reduces mean FEs by 3.88%–5.02% versus Uni and 2.37%–3.10% versus Dup-Raw, significant in all four settings (Mann–Whitney tests, Holm correction over 12 comparisons). See Section 4.1, Figure 3(b) and Appendix B.3 (Table 5).

  4. Larger populations, crossover probabilities and mutation strengths.

    We added M=200M=200, pc=0.9p_c=0.9, c=2c=2 and populations (μ,λ)=(⌈rL⌉,⌈rML⌉)(\mu,\lambda)=(\lceil rL\rceil,\lceil rML\rceil), L=ln⁡(rM)L=\ln(rM), fixing r=10r=10 with pm=min⁡c/(M−1),1p_m=\min\\{c/(M-1),1\\}, 30 independent runs and a 10710^7-FE budget. At M=200,c=1,pc=1/2M=200,c=1,p_c=1/2, both crossover variants succeed in 30/30 runs, versus 0/30 for both mutation-only controls. Dup+C averages 4.61 million FEs. It also has lower means than both mutation-only controls in all tested pc=0.9p_c=0.9 and c=2c=2 settings. Growing populations have λ>μ\lambda > \mu, outside Theorem 1's regime (Section 5, Appendix B.2).

References cited in this response:

  • Chen et al. DrNAS: Dirichlet Neural Architecture Search. ICLR, 2021.
  • Dong & Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search. ICLR, 2020.
  • Lee & Ham. AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search. CVPR, 2024.
  • Lv et al. Runtime analysis of population-based evolutionary neural architecture search for a binary classification problem. GECCO, 2024.
  • Lv et al. Runtime Analysis of Evolutionary NAS for Multiclass Classification. ICML, 2025.
  • Mellor et al. Neural Architecture Search without Training. ICML, 2021.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

Dear Reviewer xD4A,

Thank you again for your detailed review and constructive suggestions. With approximately 24 hours remaining in the discussion period, we would appreciate hearing whether our responses have addressed your concerns. If any points remain unclear, we would be happy to clarify them before the discussion closes.

Thank you again for your time!

Reviewer_2NuWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses an important theoretical question about crossover in ENAS. The population-state analysis and diversity-preserving selection are promising, but several proof steps require clarification or correction.

Critical strengths

The topic is suitable. The manuscript is well written.

Critical weaknesses
  1. The irreversibility argument in Theorem 3 needs correction. Let r = 2, M = 3, (μ, λ) = (2, 1), and c = 1, with x = ((0,0,1),(2,0,1)), y = ((1,0,0),(1,0,2)), and z = ((1,0,1),(1,0,1)). All three satisfy I = J = 2 and ε = 0. Legal mutations and Algorithm 2 permit the sequence {x,x} → {x,y} → {x,z}, moving from Case i.2 to i.3 and back to i.2. Thus, preserving distinct outer encodings does not ensure positive I-distance. Please revise this proof step.

  2. The combinatorial identity preceding Equation (20) is incorrect: C(λ+μ−1, μ) / C(λ+μ, μ) = λ/(λ+μ), where C(n,k) denotes a binomial coefficient. The manuscript instead gives μ/(λ+μ). Please revisit the resulting transition bound and Equations (21)-(22).

  3. The Phase-2 potential in Equation (26) needs a domain restriction. Its minimization includes individuals with I < N, so D₂(X) = 0 does not guarantee that one individual meets both optimality conditions. Please restrict the minimum to individuals satisfying I = N, consistently with the Phase-2 levels in Section 3.1.

  4. The manuscript acknowledges that the upper bounds may be loose. To clarify their informativeness, could the authors examine whether the mutation-only branch, occurring with probability 1/2, allows the argument of Theorem 2 to yield a tighter bound for the crossover variants?

  5. The reported mutation settings are ambiguous at M = 2. If c = 2 is used there, the stated formula gives pₘ = c/(M−1) = 2. Please clarify whether this combination was excluded or a different rate was implemented, and align the experimental description with the algorithm.

  6. Please clarify the relationship between the experiments and Theorem 1. The theorem requires μ = ω(r) and λ = ω(rM), whereas the experiments use fixed, small populations. These experiments illustrate finite-size behavior, but do not directly test the stated scaling regime.

  7. The empirical reporting could be more complete. Figure 3 shows only r = 10, although Section 5 states that r ranges from 2 to 10. Please provide results for the remaining settings and define the shaded regions, indicating whether they represent variability across runs or uncertainty in the estimated means.

Questions for authors

N/A

2 comments
AuthorsOpenReview ↗

We thank the reviewer for the careful reading of our manuscript and the constructive comments. Following your suggestions, we have revised the theoretical analysis and expanded the experiments, as detailed below.

  1. Theorem 3 and the transition from Case i.3i.3 to Case i.2i.2.

    Thank you for the counterexample. You are right that distinct outer encodings do not necessarily imply positive I\mathbb{I}-distance. We have added a secondary distance criterion among equal-fitness candidates with the same copy count. Lemma 2 guarantees that, for μ≥2\mu\geq2, if maximum-fitness candidates have different cell-wise II-vectors, Algorithm 2 retains at least two such individuals. This prevents the fallback i.3→i.2i.3\to i.2 while the best fitness is unchanged, avoiding repeated waits to recreate complementary parents. Lemma 2 appears in Section 4.2, with proofs of the lemma and Theorem 3 in Appendices A.2.4–A.2.5.

  2. The combinatorial identity and Equations (20)–(22).

    Thank you. We corrected the ratio to (λ+μ−1μ)/(λ+μμ)=λ/(λ+μ)\binom{\lambda+\mu-1}{\mu}/\binom{\lambda+\mu}{\mu}=\lambda/(\lambda+\mu) and added λ≤μ\lambda\leq\mu, so it is at most μ/(λ+μ)\mu/(\lambda+\mu). We rechecked the subsequent derivations: the other bounds retain their asymptotic forms under this condition.

  3. The domain of the Phase-2 potential.

    Thank you. We restricted the minimum defining D2(X)D_2(X) to Ix=NI_x=N in revised Equation (25), corresponding to original Equation (26).

  4. A tighter bound from the branch without crossover.

    Thank you for this helpful suggestion. We added the bound after Theorem 2, with its proof in Appendix A.2.3:

    \mathbb{E}[T]=O\left(\mu+rM\max\left\\{\lambda,\frac{\mu e^c}{c}\ln(rM)\right\\}\right).

    The proof maximizes II, then J−ϵJ-\epsilon subject to I=N=2r(M−1)I=N=2r(M-1). At deficit dd, improving one deficient cell while leaving others unchanged has probability qd=Ω(cd/(μecrM))q_d=\Omega(cd/(\mu e^c rM)). Skipping crossover preserves this event with probability qd/2q_d/2. Summing the resulting waiting costs over both phases gives the bound.

    Neither the original nor the revised analysis provides the lower bounds needed to establish a strict runtime advantage of crossover over mutation-only ENAS. We do not claim such a separation. Theorem 1 instead explains how population diversity affects the opportunities for crossover. When individuals have identical cell-wise II-contribution vectors, crossover alone leaves II unchanged. Different vectors can allow improving recombinations, but selection can remove these differences and return the population from Case i.3i.3 to Case i.2i.2. This observation motivates the diversity-preserving mechanism studied in Section 4.

  5. The mutation probability at M=2M=2.

    Thank you. The original experiments used pm=min⁡c/(M−1),1p_m=\min\\{c/(M-1),1\\}, giving pm=1p_m=1 at M=2,c=2M=2,c=2, as now clarified in Section 5.

  6. The relationship between the experiments and Theorem 1.

    After rechecking, we found the growth conditions μ=ω(r)\mu=\omega(r) and λ=ω(rM)\lambda=\omega(rM) unnecessary and removed them. Theorem 1 now requires μ≥λ\mu\geq\lambda.

    We apologize for originally reporting only small populations. Figure 3(a) and Appendix B.2 (Table 4) add (μ,λ)=(⌈rL⌉,⌈rML⌉)(\mu,\lambda)=(\lceil rL\rceil,\lceil rML\rceil), L=ln⁡(rM)L=\ln(rM), where μ\mu and λ\lambda are parent and offspring counts. We use r=10,c=1,pm=1/(M−1)r=10,c=1,p_m=1/(M-1) and 30 independent runs with a 10710^7-evaluation budget. Counts include initialization and repeated candidates. Uni means uniform fitness tie-breaking. C uses uniform crossover followed by mutation (pc=1/2p_c=1/2), and NC uses mutation only (pc=0p_c=0). All runs below succeed. Entries are mean evaluations ±\pm sample SD, in thousands.

    MM(μ,λ)(\mu,\lambda)Uni+NCUni+C
    24(55,1316)(55,1316)309.66±17.19309.66\pm17.19101.39±6.56\mathbf{101.39}\pm6.56
    50(63,3108)(63,3108)1400.08±48.371400.08\pm48.37367.80±20.57\mathbf{367.80}\pm20.57
    100(70,6908)(70,6908)5764.57±132.975764.57\pm132.971305.81±101.20\mathbf{1305.81}\pm101.20

    Crossover reduces means by 67.3%–77.3%, versus 6.7%–9.7% at (4,4)(4,4). These size-dependent settings have λ>μ\lambda > \mu and higher absolute costs, so they provide empirical evidence outside Theorem 1's regime.

  7. The remaining rr values and uncertainty reporting.

    Appendix B.2 (Table 3) adds r=2,4,6,8r=2,4,6,8 alongside r=10r=10, fixing M=24,μ=λ=4,c=1M=24,\mu=\lambda=4,c=1 with the protocol above. Dup denotes duplicate-based fitness tie-breaking. All runs succeed. Dup+C has the lowest mean throughout:

    rrUni+NCDup+NCUni+CDup+C
    21.811.841.721.49
    43.053.112.792.65
    64.124.113.863.51
    85.455.124.754.62
    106.346.215.745.64

    Means are in thousands of evaluations. Figure 3 now specifies marginal 95% bootstrap confidence intervals for means in (a) and relative reductions in (b), using 5,000 resamples. Paper tables report sample SDs.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

Dear Reviewer 2NuW,

Thank you again for your detailed review and constructive suggestions. With approximately 24 hours remaining in the discussion period, we would appreciate hearing whether our responses have addressed your concerns. If any points remain unclear, we would be happy to clarify them before the discussion closes.

Thank you again for your time!

Comments on the paper

1 comment

Dear Area Chairs and Reviewers,

Thank you for your time and constructive comments. We summarize the main additions and clarifications below. Changes are marked in blue in the uploaded PDF.

Theoretical analysis

  • Following Reviewer 2NuW, we added Lemma 2 to explain how the tie-breaking rule preserves diversity for crossover, supporting Theorem 3 (Sections 4.1–4.2, Appendices A.2.4–A.2.5).
  • Following Reviewer 2NuW, we added an alternative runtime upper bound for the crossover algorithm in Theorem 1 by analyzing progress when crossover is skipped (Section 3.2, Appendix A.2.3).
  • Following Reviewer 9vGW, we added Theorem 4 for mutation-only ENAS with the same duplicate-based tie-breaking rule (Section 4.2, Appendix A.2.6).

Experiments

  • Following Reviewer 9vGW, we added direct MCC comparisons of all four combinations of crossover and tie-breaking. At M = 100, adding crossover while keeping duplicate-based tie-breaking fixed reduces mean fitness evaluations by 13.0% (Section 5, Table 1).
  • Following Reviewers xD4A and 9vGW, we added the popular NAS-Bench-201 benchmark on CIFAR-10, CIFAR-100 and ImageNet16-120. Crossover with duplicate-based tie-breaking reduces mean capped evaluations relative to mutation-only search with uniform tie-breaking by 24.47%, 31.85% and 18.73%, respectively (Section 5, Table 2; settings in Appendix B.4).
  • Following Reviewer xD4A, we added an encoding sensitivity study. We compared the outer encoding used in our paper with the block-count encoding. With either encoding, duplicate-based tie-breaking yields lower mean evaluations than uniform tie-breaking in all four settings, with reductions of approximately 0.8%–5.0% across the tested comparisons (Section 5, Figure 3(b), Appendix B.3, Table 5).
  • Following Reviewers 2NuW and xD4A, we expanded the MCC experiments to larger populations, M = 200, additional r values, crossover probabilities and mutation strengths. The population-size comparison appears in Figure 3(a), the additional r results in Table 3, and the population, problem-size and operator comparisons in Table 4 (Section 5, Appendix B.2).

Discussion and clarifications

  • Following Reviewer 2NuW, we made the relationship between the population condition in Theorem 1 and the experimental population settings explicit (Sections 3.2 and 5).
  • Following Reviewer xD4A, we added a direct comparison of Theorems 1 and 3 to explain which part of the runtime upper bound is reduced by preserving diversity (Section 4.2).
  • Following Reviewer 9vGW, we added shortest edit path crossover to the related work and distinguished its one-step improvement analysis from our analysis of the time to reach an optimum (Section 1).
  • Following Reviewer 2NuW, we clarified the experimental mutation probability (Section 5, Appendix B.1).
  • Following Reviewers 2NuW and xD4A, we expanded the experimental descriptions and figure/table captions to state the population sizes, operator settings and numbers of runs directly (Section 5, Appendices B.1–B.4).

For details, please see our responses to each reviewer and the revised manuscript. Thank you again for your time and consideration.

Sincerely,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.