Runtime Analysis of Population-based Evolutionary Neural Architecture Search for a Binary Classification Problem

Evolutionary neural architecture search (ENAS) employs evolutionary techniques, e.g., evolutionary algorithm (EA), to design high-performing neural network architectures, and has achieved great success. However, compared to the application, its theoretical analysis is still in its infancy and only touches the ENAS without populations. In this work, we consider the (μ+λ)-ENAS algorithm (based on a general population-based EA with mutation only, i.e., (μ+λ)-EA) to find an optimal neural network architecture capable of solving a binary classification problem Uniform (with problem size n), and obtain the following mathematical runtime results: 1) by applying a local mutation, it can find the optimum in an expected runtime of O(μ + nλ/(1 - e-^λ/μ)) and Ω(μ + nλ/(1 - e^−-λ)); 2) by applying a global mutation, it can find the optimum in an expected runtime of O(μ + λc^λn/(1 - e^−-λ/μ)), and Ω(μ + λn ln ln re/ln n) for some constant c > 1. The derived results reveal that the (μ+λ)-ENAS algorithm is always not asymptotically faster than (1+1)-ENAS on the Uniform problem when λ ϵ ω(ln n/(ln ln n)). The concrete theoretical analysis and proof show that increasing the population size has the potential to increase the runtime and thus should be carefully considered in the ENAS algorithm setup.