A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914743115055104 |
|---|---|
| author | Lv, Zeqiong Qian, Chao Sun, Yanan |
| author_facet | Lv, Zeqiong Qian, Chao Sun, Yanan |
| contents | Evolutionary neural architecture search (ENAS) employs evolutionary algorithms to find high-performing neural architectures automatically, and has achieved great success. However, compared to the empirical success, its rigorous theoretical analysis has yet to be touched. This work goes preliminary steps toward the mathematical runtime analysis of ENAS. In particular, we define a binary classification problem $\textsc{UNIFORM}$, and formulate an explicit fitness function to represent the relationship between neural architecture and classification accuracy. Furthermore, we consider (1+1)-ENAS algorithm with mutation to optimize the neural architecture, and obtain the following runtime bounds: both the local and global mutations find the optimum in an expected runtime of $Θ(n)$, where $n$ is the problem size. The theoretical results show that the local and global mutations achieve nearly the same performance on $\textsc{UNIFORM}$. Empirical results also verify the equivalence of these two mutation operators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11712 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search Lv, Zeqiong Qian, Chao Sun, Yanan Neural and Evolutionary Computing Evolutionary neural architecture search (ENAS) employs evolutionary algorithms to find high-performing neural architectures automatically, and has achieved great success. However, compared to the empirical success, its rigorous theoretical analysis has yet to be touched. This work goes preliminary steps toward the mathematical runtime analysis of ENAS. In particular, we define a binary classification problem $\textsc{UNIFORM}$, and formulate an explicit fitness function to represent the relationship between neural architecture and classification accuracy. Furthermore, we consider (1+1)-ENAS algorithm with mutation to optimize the neural architecture, and obtain the following runtime bounds: both the local and global mutations find the optimum in an expected runtime of $Θ(n)$, where $n$ is the problem size. The theoretical results show that the local and global mutations achieve nearly the same performance on $\textsc{UNIFORM}$. Empirical results also verify the equivalence of these two mutation operators. |
| title | A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2401.11712 |