Runtime Analysis of Evolutionary NAS for Multiclass Classification
Zeqiong Lv, Chao Qian, Yun Liu, Jiahao Fan, Yanan Sun
Abstract
Evolutionary neural architecture search (ENAS) is a key part of evolutionary machine learning, which commonly utilizes evolutionary algorithms (EAs) to automatically design high-performing deep neural architectures. During past years, various ENAS methods have been proposed with exceptional performance. However, the theory research of ENAS is still in the infant. In this work, we step for the runtime analysis, which is an essential theory aspect of EAs, of ENAS upon multiclass classification problems. Specifically, we first propose a benchmark to lay the groundwork for the analysis. Furthermore, we design a two-level search space, making it suitable for multiclass classification problems and consistent with the common settings of ENAS. Based on both designs, we consider (1+1)-ENAS algorithms with one-bit and bit-wise mutations, and analyze their upper and lower bounds on the expected runtime. We prove that the algorithm using both mutations can find the optimum with the expected runtime upper bound of O(rM ln rM ) and lower bound of Ω(rM ln M ). This suggests that a simple onebit mutation may be greatly considered, given that most state-of-the-art ENAS methods are laboriously designed with the bit-wise mutation. Empirical studies also support our theoretical proof.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
- Searching for Efficient Transformers for Language ModelingDavid R. So, Wojciech Manke, Hanxiao Liu, Zihang Dai et al.NeurIPS 2021 · 205 citations
- Evolutionary Neural Architecture Search for Transformer in Knowledge TracingShangshang Yang, Xiaoshan Yu, Ye Tian, Xueming Yan et al.NeurIPS 2023 · 11 citations
Related papers
- FENAS: Flexible and Expressive Neural Architecture SearchRamakanth Pasunuru, Mohit BansalEMNLP Findings 2020 · 3 citations
- Neural architecture search using property guided synthesisCharles Jin, Phitchaya Mangpo Phothilimthana, Sudip RoyOOPSLA 2022 · 8 citations
- EMT-NAS: Transferring architectural knowledge between tasks from different datasetsPeng Liao, Yaochu Jin, Wenli DuCVPR 2023
- AutoSpace: Neural Architecture Search with Less Human InterferenceDaquan Zhou, Xiaojie Jin, Xiaochen Lian, Linjie Yang et al.ICCV 2021 · 11 citations
- Binarizing MobileNet via Evolution-Based SearchingHai Phan, Zechun Liu, Dang Huynh, Marios Savvides et al.CVPR 2020
