IEEE Computational Intelligence Magazine - May 2023 - 80

require considerable time and computational
resources. The high demands rise
due to the training and validation of
many network architectures, which are
the main computational bottlenecks
regarding NAS algorithm development.
NAS algorithms developed to accelerate
automated discovery, such as
parameter-sharing-based algorithms [27],
[28], [29] and single-path samplingbased
algorithms [6], [30], have recently
attracted much attention. A one-shot
supernetwork was constructed first. The
weights of the subnetworks found during
the search were all inherited from
the supernetwork, enabling the subnetworks
to obtain their weights without
training. However, the supernetwork
training process requires considerable
time, and supernetwork optimization is
difficult. The algorithms that rely on
supernetworks to completely replace the
actual subnetwork weight optimizations
are unreliable. Several studies like [31],
[32] have proven that the correlation
between subnetwork performance
obtained by the above algorithms and
the test accuracy obtained by gradient
descent calculation are both weak. In
addition, some algorithms use surrogate
models to predict the network architecture
accuracies rather than directly training
network architectures to reduce
computational consumption; examples
include PNAS [33], OnceForAll [34],
and SemiNAS [35]. The accuracy ofthe
network architecture is predicted by
constructing a predictor that can achieve
a more accurate network architecture
performance evaluation. However, the
rank order between the true and predicted
accuracy is low. Training surrogate
models also requires numerous data
samples. The 2k50k network architectures
need to be collected as the training
data to train the predictors, which means
that the cost ofwell-trained predictors is
exceptionally high.
Instead of evaluating network architecture
performance through training,
NAS algorithms that do not involve
training have been proposed. Several
training-free metrics are correlated with
the network test accuracy, and these metrics
can be directly employed as proxies
for training-based metrics in optimization
problems. These training-free metrics are
built differently for various NAS methods.
Mellor et al. [36] recently studied
the overlap between the data point activations
in untrained network architectures.
They proposed aJacobian based on
input and output data as a training-free
metric. However, the principle of this
measure has not been explicitly proven or
explained. TE-NAS [37] leverages the
NTK proposed by Jacot [38] and
Hanin [39] tomeasure the network architecture
trainability. In TE-NAS, a strong
correlation between the NTK condition
number and the network architecture test
accuracy was found, displaying good generalization
in different search spaces.
In general, NAS algorithms can be
roughly divided into reinforcement
learning (RL) approaches [28], [40],
[41] and EA-based approaches [42],
[43], [44]. Real et al. [7] provided a
large-scale comparison between EAbased
and RL-based algorithms, proving
that EA-based methods converge
faster than RL-based approaches in the
same search space. Moreover, the
experimental results in [45] showed that
EA-based designs often require fewer
computational resources than RL-based
designs. EA-based methods considers
constructing the network architecture
Algorithm 1. Overview of LoNAS
Input: Reg Block parameters, the population size N, the maximum number of evolution
rounds Max gen, the number of offspring t, and the two separation points in the
three-stage evolution process (G1 and G2).
Output: The best discovered architecture.
1: P Initialize a population with a size of N by using the encoding strategy;
2: Evaluate the fitness of the individuals in P based on the NTK;
3: i 1
4: while i Max gen do
5:
6:
7:
8:
9:
10:
11:
12:
else
P Select N individuals in P [ Q by environmental selection based on the
individual lifespan values;
end if
i i þ 1
13: end while
14: return The architecture with the best test accuracy.
80 IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2023
as a combinatorial optimization problem
through EA, with individuals in the
population representing network architectures.
During evolution, the network
architectures pass through crossover and
mutation operators, and the individuals
with the best fitness are selected as the
optimal solution at the end of the
evolution.
III. Methods
The goal of LoNAS is to search for
highly accurate neural network architectures
with few parameters, using little
search time and computational resources.
An overview of the LoNAS algorithm
is presented first in this section.
Then, the details of LoNAS are introduced,
including the Reg Block design,
an expanded search space based on a
variable-architecture encoding strategy,
a fitness evaluation of individuals based
on a training-free proxy (i.e., the NTK
strategy), a three-stage EA based on
multiple-criteria environmental selection,
and a set ofmutation operators for
Reg Block.
A.Algorithm Overview
An overview of the proposed LoNAS
approach is summarized in Algorithm 1.
LoNAS starts with a population initialized
with random individuals (Line 1).
parents Select t parent individuals in P based on tournament selection;
Q Generate t offspring individuals from parents with mutation operators;
if i G1 or G2 i then
P Select N individuals in P [ Q by environmental selection based on the
NTK;
IEEE Computational Intelligence Magazine - May 2023

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - May 2023
