Research map / Learning theory and algorithms / Sample complexity
Runtime Analysis of Evolutionary NAS for Multiclass Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a multiclass classification benchmark (MCC) with a closed-form fitness function and a two-level cell/block search space, then proves runtime bounds for (1+1)-ENAS with one-bit and bit-wise mutations.
Problem
Theoretical understanding of runtime of evolutionary neural architecture search (ENAS) for multiclass classification, where prior runtime analyses were limited to binary classification and a restrictive search space.
Approach
Builds a multiclass benchmark (MCC) on the unit circle whose fitness is a closed-form area-based accuracy of a cell/block architecture, and a two-level search space with solution length M-1 triplets that admits standard EA mutations; runtime of (1+1)-ENAS is then analyzed via multiplicative drift and fitness levels, showing one-bit and bit-wise mutations share the same bounds.
Key results
- Proves upper bound O(rM ln(rM)) and lower bound Omega(rM ln M) on expected runtime of (1+1)-ENAS for MCC with one-bit and bit-wise mutations.
- Empirical runs (1,000 independent runs, M from 2 to 24, r from 2 to 10) show one-bit and bit-wise outer mutations differ only by a constant factor.
- Extended experiments with population-based ENAS and crossover reportedly show one-bit mutation comparable to bit-wise mutation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use one-bit instead of bit-wise outer-level mutation (ablation) | (1+1)-ENAS · Mcc | expected runtime: O\left(rM\ln(rM)\right); \Omega(rM\ln{M}) | No clear effect |
| Use one-bit instead of bit-wise outer-level mutation (ablation) | ENAS with four mutation settings · Mcc | average number of generations | No clear effect |
| Use global instead of local inner-level mutation (ablation) | ENAS with four mutation settings · Mcc | average number of generations | No clear effect |
| Use one-bit outer-level mutation with local or global inner-level mutation (ablation) | (1+1)-ENAS · Mcc | expected runtime: O\left(rM\ln(rM)\right) | Helped |
| Use bit-wise outer-level mutation with local or global inner-level mutation (ablation) | (1+1)-ENAS · Mcc | expected runtime: O(rM\ln(rM)) | Helped |
Surprising findings
- One-bit and bit-wise outer-level mutations give the same asymptotic runtime bounds, suggesting the simpler one-bit mutation may be preferred in ENAS design.
Limitations
- Assumes the optimal weights of each evolved architecture are obtained during fitness evaluation, so training is idealized.
- Benchmark restricted to 2-D inputs on the unit circle with sector/triangle/segment decision regions.
- Analysis of the main theory is limited to mutation-only (1+1)-ENAS; population and crossover are only studied empirically.
Experimental setup
Datasets: MCC benchmark (synthetic, unit circle)
Benchmarks: MCC
Metrics: expected number of generations to optimum
Baselines: (1+1)-ENAS with bit-wise outer mutation (1+1)-ENAS with one-bit outer mutation (lambda+lambda)-ENAS with one-point crossover (lambda+lambda)-ENAS with uniform crossover
Builds on: Lv et al. 2024 binary-classification ENAS runtime analysis multiplicative drift analysis fitness-level method
Closest papers by meaning
- EG-NAS: Neural Architecture Search with Fast Evolutionary Exploration (AAAI 2024 · similarity 0.89)
- Efficient Neural Architecture Search via Parameters Sharing (ICML 2018 · similarity 0.88)
- Neural Architecture Generator Optimization (NeurIPS 2020 · similarity 0.87)
- EcoNAS: Finding Proxies for Economical Neural Architecture Search (CVPR 2020 · similarity 0.87)
- Unifying and Boosting Gradient-Based Training-Free Neural Architecture Search (NeurIPS 2022 · similarity 0.87)
- Insights from the Use of Previously Unseen Neural Architecture Search Datasets (CVPR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.