# Evolutionary Neural Cascade Search across Supernetworks

Alexander Chebykin  Centrum Wiskunde & InformaticaAmsterdamThe Netherlands
<EMAIL_ADDRESS>,  Tanja Alderliesten  Leiden University Medical
CenterLeidenthe Netherlands<EMAIL_ADDRESS>and  Peter A. N. Bosman
Centrum Wiskunde & InformaticaAmsterdamthe Netherlands TU DelftDelftThe
Netherlands<EMAIL_ADDRESS>
(2022)

###### Abstract.

To achieve excellent performance with modern neural networks, having the right
network architecture is important. Neural Architecture Search (NAS) concerns
the automatic discovery of task-specific network architectures. Modern NAS
approaches leverage supernetworks whose subnetworks encode candidate neural
network architectures. These subnetworks can be trained simultaneously,
removing the need to train each network from scratch, thereby increasing the
efficiency of NAS.

A recent method called Neural Architecture Transfer (NAT) further improves the
efficiency of NAS for computer vision tasks by using a multi-objective
evolutionary algorithm to find high-quality subnetworks of a supernetwork
pretrained on ImageNet. Building upon NAT, we introduce ENCAS — Evolutionary
Neural Cascade Search. ENCAS can be used to search over multiple pretrained
supernetworks to achieve a trade-off front of cascades of different neural
network architectures, maximizing accuracy while minimizing FLOPs count.

We test ENCAS on common computer vision benchmarks (CIFAR-10, CIFAR-100,
ImageNet) and achieve Pareto dominance over previous state-of-the-art NAS
models up to 1.5 GFLOPs. Additionally, applying ENCAS to a pool of 518
publicly available ImageNet classifiers leads to Pareto dominance in all
computation regimes and to increasing the maximum accuracy from 88.6% to
89.0%, accompanied by an 18% decrease in computation effort from 362 to 296
GFLOPs. Our code is available at https://github.com/AwesomeLemon/ENCAS

Neural Architecture Search, Deep Learning, Computer Vision, AutoML,
Evolutionary Computation

††journalyear: 2022††copyright: rightsretained††conference: Genetic and
Evolutionary Computation Conference; July 9–13, 2022; Boston, MA,
USA††booktitle: Genetic and Evolutionary Computation Conference (GECCO ’22),
July 9–13, 2022, Boston, MA, USA††doi: 10.1145/3512290.3528749††isbn:
978-1-4503-9237-2/22/07††ccs: Computing methodologies Neural networks††ccs:
Computing methodologies Genetic algorithms††ccs: Computing methodologies
Ensemble methods

##  1\. Introdution

In recent years, deep neural networks have been successfully applied in
domains ranging from text summarization (Brown et al., 2020) to medical image
segmentation (Isensee et al., 2021). Much of this success has been enabled by
task-specific neural network architectures that are designed manually while
making use of expert knowledge. The research direction of Neural Architecture
Search (NAS) (Zoph and Le, 2016) has the goal of making architecture design
automatic and data-driven. Tremendous progress has been made since the first
approaches: performance of the found models improved (Liu et al., 2018; Sharma
et al., 2020), their size decreased (Pham et al., 2018; Dong and Yang, 2019a)
(smaller models usually work faster and require less storage space), and the
search process itself became much more efficient (with required GPU-hours
decreasing from tens of thousands (Real et al., 2019) to single-digit numbers
(Stamoulis et al., 2019)).

These search efficiency gains can mostly be attributed to the idea of weight
sharing via a supernetwork (Pham et al., 2018) (with performance prediction
(Baker et al., 2017; White et al., 2021) also playing a role). Instead of
training the weights of each candidate architecture from scratch, a
supernetwork is constructed such that each architecture in the search space is
a subset of the supernetwork (see Fig. 1). To evaluate the quality of an
architecture, the weights of the relevant part of the supernetwork are copied.
With various architectures potentially sharing the same operations (e.g.
convolution (LeCun et al., 1995), attention (Bahdanau et al., 2014)), the
amount of training needed decreases drastically.

However, by requiring that each architecture is a path within a supernetwork,
the supernetwork approach inherently limits the diversity of architectures
that can be produced. Thus, the manual choice of which supernetwork to use for
the automated NAS procedure plays a large role, as it restricts the search
space before the search algorithm even starts. With the growing number of
available supernetworks, the issue of choosing the supernetwork is becoming
increasingly important, and yet, to the best of our knowledge, there exists no
method taking it into account.

There are many ways to improve neural network performance that are different
from NAS. Ensembling (Rokach, 2010) is one such technique that involves
passing the same input through several different models and combining their
predictions to get a better final prediction. It has been shown to work well
if the models’ mistakes are independent (Esposito and Saitta, 2003), which is
helped by the models being different from each other (Wichard et al., 2003).
NAS has been used (Zaidi et al., 2021; Chen et al., 2021) to produce models
that together make a good ensemble. Modern supernetwork-based approaches seem
very fitting to this purpose because they do not incur additional training
costs for ensembles of arbitrarily large size (once a supernetwork is trained,
weights for trained subnetworks can be extracted from it and used without
additional retraining111This holds for modern state-of-the-art approaches (Cai
et al., 2020; Sharma et al., 2020; Wang et al., 2021) but does not hold for
all, especially older, approaches (Liu et al., 2018; Stamoulis et al.,
2019).).

Figure 1. A schematic of a generic supernetwork.

Cascading (Viola and Jones, 2001) is a particular case of ensembling with the
focus on efficiency: whereas an ensemble requires that every input is
processed by every model, a cascade proceeds in a sequential manner, invoking
a larger model only if the predictions of smaller models are not confident
enough (judged by the confidence function, see Section 2.3 for details). Thus,
easy inputs consume less computational resources, while harder inputs can
still be predicted well by utilizing every model in the cascade. Despite the
potential of cascades to produce efficient and effective models, they remain
underexplored in the context of deep learning (Wang et al., 2020), and in
particular no work has yet been done on combining NAS with cascade search.

To perform any kind of NAS, efficient search algorithms are indispensable.
Evolutionary Algorithms (EAs) are particularly fit to the task, as they do not
require the search space to be continuous, are known to solve real-world
problems efficiently (Chiong et al., 2012), and excel in solving multi-
objective and dynamic problems (Van Veldhuizen and Lamont, 1998; Singh and
Deb, 2006; Branke and Schmeck, 2003).

Driven by the observations above, in this paper we present an algorithm called
Evolutionary Neural CAscade Search (ENCAS). ENCAS is supernetwork-based and
designed to take advantage of various pretrained supernetworks. ENCAS can
search over a user-specified set of arbitrary supernetworks that may have e.g.
different operations or numbers of layers (the only restriction being that
subnetworks extracted from a supernetwork require no retraining). Our
algorithm is multi-objective with the goal of finding models on the optimal
effectivity-efficiency trade-off front.

The main contributions of our paper are threefold:

  * •

This work is the first to research the combination of NAS and cascades.

  * •

This work is the first to investigate the feasibility of using several
different supernetworks in NAS. We explore whether the additional diversity
they provide is helpful for creating cascades.

  * •

The ENCAS algorithm is introduced to search for efficient and effective
cascades.

##  2\. Related work

###  2.1. Neural Architecture Search

The first methods to learn neural network architectures trained each candidate
architecture from scratch, taking tens of thousands of GPU hours (Zoph and Le,
2016). ENAS (Pham et al., 2018) introduced the ideas of weight sharing and
supernetworks, which drastically decreased search costs. Multiple algorithms
followed, most famously DARTS (Liu et al., 2018) that reformulated the problem
of operation selection as a continuous one, achieving great efficiency.

However, supernetwork weights were discarded after NAS, with the final model
being retrained from scratch (because it led to better results). This becomes
costly when more than one model is required, e.g. considering both server-
based and smartphone-based deployment. OnceForAll (OFA) (Cai et al., 2020)
introduced an algorithm for training supernetwork weights such that they could
be used in extracted subnetworks without any further training . AttentiveNAS
(Wang et al., 2021) and AlphaNet (Sharma et al., 2020) introduced training
techniques that lead to even better performance (albeit using a different
search space).

Neural Architecture Transfer (Lu et al., 2021) (NAT) is an approach for fine-
tuning a pretrained supernetwork for smaller datasets. The key difference from
the previous approaches is that the architectures are adapted together with
the weights in a multi-objective search procedure, trading off size and
accuracy. The main idea is training only subnetworks close to the currently
known trade-off front. To this end, a population of networks is evolved by
Non-dominated Sorting Genetic Algorithm III (NSGA-III) (Deb and Jain, 2013), a
prominent many-objective EA. In this work, we aim to reproduce and to build
upon NAT. It should be noted that NAT uses two sets of supernetwork weights
that share the same search space222This was not clear to us from (Lu et al.,
2021), but it was explained to us in private communication with the authors.;
in contrast, in this work we are primarily interested in supernetworks that
represent different search spaces.

###  2.2. Search for architectures of neural ensembles

Neural Ensemble Search (Zaidi et al., 2021) (NES) is the first approach to
search architectures of neural ensembles. It trained multiple networks
separately, without weight sharing. The follow-up work, Multi-headed Neural
Ensemble Search (Narayanan et al., 2021) (MH-NES), utilizes weight sharing by
having different ensemble members share first layers of the network. MH-NES
achieves gains in robustness, search efficiency and model efficiency. Neural
Ensemble Architecture Search (NEAS) (Chen et al., 2021) is a similar approach
with the key idea of gradual removal of the least promising operations from
the supernetwork.

Neural Ensemble Search via Sampling (NESS) (Shu et al., 2021) is supernet-
based but does not require the ensemble models to have the same first layers.
For this, a supernetwork is first trained, then subnetworks are sampled via
novel sampling algorithms.

Our algorithm, ENCAS, substantially differs from all the ones discussed above.
Firstly, ENCAS searches for architectures of cascades, for which no prior work
exists (to the best of our knowledge). Secondly, ENCAS is truly multi-
objective, with a single run producing multiple networks on a trade-off front
of model size and performance, whereas NES, MH-NES, and NESS do not directly
optimize model efficiency; NEAS uses model size as a constraint in single-
objective optimization, which thus needs to be run once for each target model
size. Thirdly, none of the existing algorithms take advantage of pretrained
supernetworks, while we purposefully design our algorithm to rely on them,
bearing in mind that pretraining plays a huge role in the success of deep
learning approaches (Donahue et al., 2014). Finally, all existing algorithms
require the user to specify the ensemble size in advance. Our algorithm has
the _maximum_ cascade size as a hyperparameter, meaning that it can output
cascades with fewer networks if adding more networks does not improve the
performance.

###  2.3. Cascades of neural networks

As mentioned, cascading is a way of efficiently combining multiple available
models. It requires the user to choose a confidence function and confidence
thresholds. The confidence function estimates how confident a model is in its
prediction for a specific input. An example of that could be the maximum
predicted probability or the gap between the largest and the second-largest
logit values (Streeter, 2018). The confidence thresholds are used to decide
when to stop evaluation and to return the current output. A cascade operates
sequentially in the following way: the current model makes a prediction and a
confidence value for it is determined by the confidence function; if this
value is above the confidence threshold for the current model, the cascade is
terminated, otherwise the process is repeated for the next model. Note that
the output of a cascade can be either the output of the last used model
(Streeter, 2018) (i.e. the outputs of unconfident models are discarded), or
the averaged outputs of all the used models (Wang et al., 2020). We follow
(Wang et al., 2020) in using the averaged outputs.

Cascades are popular in machine learning (Kukenys and McCane, 2008; Xu et al.,
2014), but in deep learning there are only a few works utilizing them (Cai et
al., 2015; Angelova et al., 2015). Recently, (Wang et al., 2020) pointed out
that cascades can dominate single models in terms of performance, efficiency,
and training time. Cascades in (Wang et al., 2020) were constructed via an
exhaustive search of a small search space of predefined networks.

GreedyCascade (Streeter, 2018) achieved good results by designing an efficient
greedy algorithm for cascade selection from a somewhat larger number of
networks. GreedyCascade has a fundamental limitation: by construction, it
cannot produce a cascade that would perform better than the best model in the
model pool. Our algorithm does not have this limitation in its design. In
addition, GreedyCascade scales quadratically in the number of networks.

Our algorithm searches in a search space that is substantially larger than
ever used before for cascade search (it contains hundreds of networks instead
of dozens). Also, ENCAS is multi-objective and requires only a single run to
create the trade-off front, unlike the exhaustive search procedure of (Wang et
al., 2020).

###  2.4. Evolutionary algorithms

An EA is a population-based optimization algorithm that relies on the ideas of
(1) fitness-based selection and (2) variation (most often mutation and
crossover, i.e. information transfer between solutions in the population). EAs
achieve SOTA results on a variety of benchmark and real-world problems (Chiong
et al., 2012; Petchrompo et al., 2022; Bouter et al., 2019).

In this paper, we use NSGA-III (Deb and Jain, 2013) (as part of NAT) and the
Multi-objective Gene-pool Optimal Mixing Evolutionary Algorithm (MO-GOMEA)
(Luong et al., 2014). NSGA-III relies on non-dominated sorting and pre-
supplied reference points to keep the population spread-out in the objective
space. The two key ideas behind MO-GOMEA are linkage learning (which leads to
dependent variables being exchanged between solutions as a single group) and
Gene-pool Optimal Mixing (which ensures that crossover always leads to a
fitness improvement). Since we use the algorithm without any modifications, we
refer the interested reader to (Luong et al., 2014; Thierens and Bosman, 2011)
for details. We choose to use this algorithm because it performs well in many
problems (Rodrigues et al., 2016; Luong et al., 2015) and because it does not
require setting any hyperparameters (such as population size, crossover type,
or mutation rate).

##  3\. Methods

###  3.1. Searching for cascades of dynamic size

Let us assume that a supernetwork has been trained via the NAT procedure. In
addition to the supernetwork weights, the procedure generates a trade-off
front of network architectures. The architectures from this front will be used
in ENCAS.

Creating a cascade of a specific size out of a predefined model pool comes
down to selecting the appropriate sequence of models, and their confidence
thresholds. Let us focus on the models first. Each out of $N$ models can be
encoded as a categorical value $1..N$. To consider cascades with fewer models
(or even a single model), we add the value $0$ to encode a ”no operation”
model — a model that does nothing. Then, a solution to the problem of
searching for a cascade of maximum size $k$ can be encoded as a list of $k$
values, each ranging from $0$ to $N$. In the interest of robustness we do not
search for the weights of the models in the cascade, and take a simple average
of their outputs instead.

As to the confidence threshold values, they are encoded as ${k-1}$ additional
categorical variables. In our experiments we use 51 possible values from $0.0$
to $1.0$ with step size $0.02$. If all thresholds are equal to $1$, the
cascade becomes an ensemble, since the confidence of any model will always be
smaller than $1$, and thus all the models will be used.

A visual representation of a solution can be seen in Figure 2.

Figure 2. Representation of a solution for ENCAS.

To evaluate a solution, every subsequent model is used to only update
probabilities of inputs for which previous models were not confident (once the
confidence for an input is above the current threshold, cascading stops). The
final probabilities are used as cascade predictions to evaluate its
performance. The FLOPs of a cascade are computed as a weighted sum of the
FLOPs of all the models in the cascade, where each weight is the fraction of
the total number of inputs that this model was used on. Since the models in
the model pool are known in advance, their outputs on the validation set can
be precomputed, which leads to fast search times of under 1 GPU-hour even on a
large dataset (e.g. ImageNet) and with hundreds of base models to choose from.

Note that this approach is trivial to extend to multiple supernetworks by
adding the models from the trade-off fronts of all the supernetworks to the
model pool. Since the algorithm relies on network outputs, the problem of
different supernetworks having different operations is side-stepped.

Any multi-objective search algorithm can be run to maximize validation
accuracy and minimize FLOPs. We use MO-GOMEA (Luong et al., 2014). Pseudocode
of ENCAS is listed in Algorithm 1.

Input : Supernetworks $\\{S_{i}\\}$, possible thresholds $\\{t_{i}\\}$,
maximum cascade size $k$

model_pool = []

for  _$S_{i}$ in $\\{S_{i}\\}$_ do

trade_off_fronti = NAT($S_{i}$)

model_pool = model_pool $\cup$ trade_off_fronti

fitness_func = make_fitness_func(model_pool, $\\{t_{i}\\}$, $k$)

/* make_fitness_func defines the procedure for decoding and encoding the
values (see Fig. 2), and for evaluating a solution, i.e. a cascade (see
Section 2.3). */

cascades = MO-GOMEA(fitness_func)

return cascades // the trade-off front

Algorithm 1 ENCAS

Empirically, we observed that ENCAS finds hundreds of cascades. To reduce that
number and to combat overfitting, the trade-off front found by ENCAS is
filtered: we traverse the non-dominated front from least accurate to most
accurate cascades, and a cascade is kept if its accuracy on the validation set
after rounding to the first significant digit is higher than the accuracy of
the previous cascade.

###  3.2. Joint training and cascade search

In ENCAS, only the models from the trade-off front of each supernetwork are
considered. This means that ENCAS works with models that are very good on
their own, but it also means that it cannot create cascades of models that
might be subpar individually but extremely good together. Models with weights
that complement each other in this way may not even exist in separately-
trained supernetworks, so ideally the training of a supernetwork and the
cascade search should happen simultaneously. To investigate whether this idea
is feasible, we construct a version of ENCAS called ENCAS-joint (indicating
that training and search are performed jointly).

ENCAS-joint extends NAT to training several different supernetworks
simultaneously. Whereas in NAT a solution represents an architecture of a
single model, in ENCAS-joint a solution represents architectures of all the
models in a cascade, their target positions, and the threshold values.
Confidence thresholds are restricted to 10 possible values from $0.1$ to $1.0$
with step size $0.1$ to decrease the search space size; the confidence
threshold of the last network is not used. These per-supernetwork
representations are concatenated to encode the whole cascade. Figure 3
visualizes the encoding.

Figure 3. Representation of a solution in ENCAS-joint.

Note that our encoding of the order of the networks is generally inefficient
(i.e. a permutation would be more efficient), but since we use a small number
of supernetworks (5), the number of possible orderings is quite small, and our
Cartesian encoding should suffice.

Before evaluating a cascade, the networks are ordered (with ties broken
arbitrarily), after which the cascade is evaluated as usual. NAT requires
defining a surrogate that predicts the fitness of an architecture. To extend
this to multiple supernetworks in a simple way, we create such a surrogate for
each supernetwork used, and an additional surrogate that combines outputs of
supernetwork-wise surrogates for a prediction for the whole cascade. Yet
another surrogate is used to estimate the FLOPs count for a cascade from FLOPs
of individuals models, target positions, and thresholds (this is necessary
because changing thresholds or the order of networks impacts not only its
performance but also the FLOPs count). Each of the surrogates is a Radial
Basis Function (RBF) (Broomhead and Lowe, 1988) ensemble, the same as in NAT.

Each supernetwork is trained separately based on which subnetworks from it are
present in the population. In order not to disadvantage supernetworks that
might require more training to achieve good accuracy, we train all the
supernetworks for an equal number of steps. To avoid tuning hyperparameters of
NSGA-III to the new scenario, we exchange it for MO-GOMEA, for which no
hyperparameters are tuned.

Note that this approach has a limitation of not allowing a cascade to contain
several models from the same supernetwork. Therefore, it is possible to
further improve results by running ENCAS on the supernetworks trained by
ENCAS-joint (we refer to this combination as ENCAS-joint+). In the next
section we compare all versions of our algorithm.

##  4\. Experiments

We conduct experiments on established computer vision benchmark datasets:
ImageNet (ILSVRC2012) (Russakovsky et al., 2015), CIFAR-10 (Krizhevsky et al.,
2009), and CIFAR-100 (Krizhevsky et al., 2009). In our experiments, we
consider the bi-objective problem of maximizing top-1 accuracy while
minimizing the FLOPs count. Note that hyperparameter selection and all search
procedures were performed on the validation subsets, while the experimental
results are reported on the test sets. This means that a trade-off front that
is monotonous when evaluated on the validation set often becomes non-
monotonous when evaluated on the test set. Since one should not use the test
set to select models, we show all the models, even if they are dominated once
the test accuracy is considered.

The validation sets for CIFAR-10 and CIFAR-100 consist of 10,000 images
randomly split off from the training set (that contain 50,000 images; test
sets contain 10,000 images). For ImageNet we rely on the pretrained networks
that use the whole training set and report the results on the ILSVRC2012
validation set, as is established practice, since the true test set is not
publicly available. Images seen during training cannot be used during the
search because their activations have different statistics (Streeter, 2018),
and for comparability our results should be reported on the ILSVRC2012
validation set (which is treated as the test set). As the actual validation
set, we therefore used 20,683 images from ImageNetV2 (Recht et al., 2019),
which is a dataset designed to match the ImageNet collection procedure as
closely as possible333ImageNetV2 contains three sets of 10,000 images that
were collected slightly differently, we use images from all three sets:
removing duplicates gives 20,683 images.. We would prefer to avoid using this
additional data, but cannot; as the number of these images is only 1.6% of the
ImageNet training set size, we assume that the unfair advantage we gain by
using it is negligible.

We use the normalized hypervolume indicator (Zitzler et al., 2003) as a metric
of the quality of a trade-off front (see Appendix F for details). Every
experiment is run 10 times, mean and standard deviation are reported. We plot
the median run (in terms of hypervolume), along with a shaded area delimited
by the worst and best fronts achieved over all the runs. Appendix A contains
our hyperparameters. Search time is measured on a single Nvidia 2080TI GPU.
For statistical testing we use the Wilcoxon signed-rank test (Wilcoxon, 1992)
with Bonferroni correction (Dunn, 1961) (target $p$-value=0.01, 20 tests,
corrected $p$=0.0005, mentions of statistical significance in the text imply
smaller $p$, all $p$-values are reported in Appendix E).

Our code is public444https://github.com/AwesomeLemon/ENCAS. We have worked
with our own implementation of NAT because we did not have access to the
authors’ code of NAT that was used for the NAT article.

###  4.1. Baseline supernetworks

We are interested in utilizing pretrained supernetworks, as training one from
scratch takes on the order of thousands of GPU-hours (Cai et al., 2020).
Unfortunately, many papers do not release either code or pretrained weights.
As more supernetworks become available in the future, the value of searching
across supernetworks should only increase.

In our experiments we rely on five different supernetworks pretrained on
ImageNet: AttentiveNAS (Wang et al., 2021), AlphaNet (Sharma et al., 2020),
ProxylessNAS (Cai et al., 2019), OFA-w1.0 (Cai et al., 2020), OFA-w1.2 (Cai et
al., 2020). All of them are built from inverted residual blocks (Sandler et
al., 2018). Moreover, ProxylessNAS, OFA-w1.0, OFA-w1.2 have the same search
space, with only width multipliers being different (to get the actual number
of neurons in a layer, the base number of neurons is multiplied by the width
multiplier). AttentiveNAS and AlphaNet are from the same search space, but the
weights were trained via different approaches.

To adapt a supernetwork to CIFAR-10 and CIFAR-100, we apply the NAT procedure
for each supernetwork separately. This produces trade-off fronts of models,
which in the following sections will be used for cascade construction. For
CIFAR-10 and CIFAR-100 we also reproduce NAT with its original hyperparameters
using OFA-w1.0 and OFA-w1.2 (due to computational constraints, we do not
reproduce NAT for ImageNet). For ImageNet, there is no need to further update
the weights, however the trade-off front still needs to be found. For this
reason, we run a version of NAT with no training and no reevaluation of the
already evaluated networks.

(a) CIFAR-10

(b) CIFAR-100

(c) ImageNet

Figure 4. Results of running NAT (Lu et al., 2021) with different
supernetworks on CIFAR-10, CIFAR-100, ImageNet.

Results of using NAT with each supernetwork are presented in Fig. 4. It can be
seen that the choice of the supernetwork impacts the resulting trade-off front
significantly, with supernetworks that perform better on ImageNet also
performing better on CIFAR-10 and CIFAR-100, as expected (Kornblith et al.,
2019). Additionally, our reproduced NAT achieves results inferior to those
reported in (Lu et al., 2021), even after we introduced changes that were not
in the article but suggested by the authors in private communication (see
Appendix A). This prompted us to look for better hyperparameters, which are
used in all our experiments (including those in Fig. 4). With these
hyperparameters, search time is 30 GPU-hours for OFA-w1.0, OFA-w1.2, or
ProxylessNAS, and 45 GPU-hours for AlphaNet or AttentiveNAS.

###  4.2. Cascading best NAT results

Figure 5 and Tables 1, 2, 3 show that using ENCAS on the NAT results with the
single best supernetwork leads to the models on the fronts becoming more
efficient across all datasets, with hypervolumes increasing (statistically
significant; difference in maximum accuracy is not statistically significant).
Visually, the effect is small on ImageNet, and noticeable on CIFAR-10 and
CIFAR-100.

(a) CIFAR-10

(b) CIFAR-100

(c) ImageNet

Figure 5. Comparing ENCAS to the baselines.

###  4.3. Cascading all NAT results

The next question is whether using supernetworks other than the best one will
improve the results of ENCAS. As shown in Figure 5, the results are strongly
improved, with the differences in hypervolume and maximum accuracy to the best
NAT baseline (and to ENCAS with 1 supernetwork) being statistically
significant. We hypothesize that inclusion of better and more diverse
supernetworks would make the gap even larger. Search time of ENCAS is 1 GPU-
hour (with approximately 300 base models). Since we report all the cascades
found by ENCAS (several dozen), we do not name them, but for the ease of
reference we name a subset (see Appendix D).

###  4.4. Comparison to SOTA

We compare ENCAS with the SOTA cascade search algorithm GreedyCascade
(Streeter, 2018) by applying it to the same model pool. As can be seen in
Figure 5, ENCAS matches the performance of GreedyCascade for smaller FLOPs on
all datasets, and can find cascades with better accuracy than the best
baseline model, which GreedyCascade cannot do. Note that the runtime of both
algorithms (under 1 hour) is negligible in comparison to the supernetwork
adaptation time (tens of hours). Differences in hypervolume and maximum
accuracy between ENCAS and GreedyCascade are statistically significant.

Table 1. ImageNet performance, ”acc.” is top-1 accuracy. The method producing the highest accuracy is in bold.  Method |  Hyper- volume |  Max acc. |  Max MFLOPs
---|---|---|---
EfficientNet B0-B3 (Tan and Le, 2019) | 0.464 | 81.6 | 1800
EfficientNet C0-C3 (Wang et al., 2020) | 0.482 | 82.2 | 1800
MobileNetV3 (Howard et al., 2019) | 0.396 | 76.6 | 350
OFA (#75) (Cai et al., 2020) | 0.451 | 80.0 | 595
NEAS (Chen et al., 2021) | 0.458 | 80.0 | 574
NSGANetV2 (Lu et al., 2020) | 0.477 | 80.4 | 593
AlphaNet (Sharma et al., 2020) | 0.490 | 80.8 | 709
BigNAS (Yu et al., 2020) | 0.480 | 80.9 | 1040
NAT (best) (Lu et al., 2021) | 0.506±0.001 | 81.69±0.02 | 1962±33
GreedyCascade (Streeter, 2018) | 0.520±0.002 | 81.72±0.11 | 927±36
ENCAS (1 supernet) | 0.509±0.001 | 81.78±0.05 | 1929±424
ENCAS (5 supernets) | 0.537±0.001 | 82.72±0.10 | 2616±221
Table 2. CIFAR-100 performance, ”acc.” is top-1 accuracy. The method producing the highest accuracy is in bold.  Method |  Hyper- volume |  Max acc. |  Max MFLOPs
---|---|---|---
EfficientNet B0-B3 (Tan and Le, 2019) | 0.664 | 89.9 | 1800
NSGANetV2 (Lu et al., 2020) | 0.658 | 88.3 | 796
GDAS (Dong and Yang, 2019b) | — | 81.87 | 519
SETN (Dong and Yang, 2019a) | — | 82.75 | 722
NAT (reproduced) (Lu et al., 2021) | 0.523±0.012 | 81.53±0.54 | 682±298
NAT (best) (Lu et al., 2021) | 0.659±0.004 | 87.94±0.23 | 1277±287
GreedyCascade (Streeter, 2018) | 0.665±0.005 | 87.25±0.25 | 341±30
ENCAS (1 supernet) | 0.663±0.005 | 88.09±0.21 | 1051±353
ENCAS (5 supernets) | 0.699±0.003 | 88.96±0.17 | 1401±420
ENCAS-joint | 0.681±0.005 | 88.55±0.19 | 6678±1735
ENCAS-joint+ | 0.701±0.005 | 89.10±0.22 | 1750±418

Our results are also compared with those of previous efficient NAS algorithms
(see Tables 1, 2, 3). Fig. 6 shows that the trade-off fronts produced by ENCAS
dominate other NAS approaches under 1.5 GFLOPs across the datasets. But it can
also be seen that for CIFAR-100 while ENCAS is on par with EfficientNet-B0 to
B2, it is outperformed by B3, even though the supernetworks we use outperform
EfficientNet B0 to B3 on ImageNet. This may occur because training an
individual network is much easier than training a supernetwork (in our
experience, training a supernetwork is hard due to subnetworks having to share
both weights and hyperparameters).

Note that we do not compare search times of different algorithms because the
corresponding publications often report times that are not comparable due to
e.g. using different hardware, not accounting for supernetwork training or
final network retraining time. A fair comparison would require us to run all
the algorithms, for which we lack compute. For future reference, the runtime
associated with each part of our pipeline is mentioned in the section
describing it.

(a) CIFAR-10

(b) CIFAR-100

(c) ImageNet

Figure 6. Comparing ENCAS with SOTA NAS algorithms.

Table 3. CIFAR-10 performance, ”acc.” is top-1 accuracy. The method producing the highest accuracy is in bold.  Method |  Hyper- volume |  Max acc. |  Max MFLOPs
---|---|---|---
EfficientNet B0-B2 (Tan and Le, 2019) | 0.863 | 98.4 | 1000
NSGANetV2 (Lu et al., 2021) | 0.904 | 98.4 | 468
GDAS (Dong and Yang, 2019b) | — | 97.18 | 519
SETN (Dong and Yang, 2019a) | — | 97.31 | 722
DARTS (Liu et al., 2018) | — | 97.24 | 547
NAT (reproduced) (Lu et al., 2021) | 0.899±0.003 | 96.80±0.13 | 361±119
NAT (best) (Lu et al., 2021) | 0.911±0.002 | 98.46±0.08 | 1390±274
GreedyCascade (Streeter, 2018) | 0.935±0.002 | 98.31±0.05 | 191±16
ENCAS (1 supernet) | 0.911±0.002 | 98.45±0.09 | 698±321
ENCAS (5 supernets) | 0.941±0.002 | 98.60±0.09 | 749±298
ENCAS-joint | 0.935±0.002 | 98.68±0.04 | 4858±1126
ENCAS-joint+ | 0.943±0.002 | 98.68±0.08 | 1060±444

###  4.5. Joint training and cascade search

Is joint weight training and search of cascade architectures beneficial? In
Fig. 7 we can see that ENCAS-joint finds a trade-off front that is worse than
the one found by ENCAS. This likely happens due to the increased size of the
search space. However, the trade-off front found by ENCAS-joint is better than
the best NAT one.

(a) CIFAR-10

(b) CIFAR-100

Figure 7. Investigating benefits of joint training and search.

We further see that ENCAS-joint+ (running ENCAS on the supernetworks trained
by ENCAS-joint) improves upon ENCAS-joint on both CIFAR-10 and CIFAR-100. But
is it better than running ENCAS on separately trained supernetworks? Although
ENCAS-joint+ appears to outperform ENCAS in terms of hypervolume and maximum
accuracy (see Tables 2, 3), these results are not statistically significant.

Note that these experiments are not performed on ImageNet due to limitations
in computational power. Training supernetworks jointly is computationally
intensive in general (search time of ENCAS-joint is 240 GPU-hours) while also
lacking flexibility, as adding or removing a network means restarting the
whole process from scratch. Given inconclusiveness of improvements brought by
ENCAS-joint+, we recommend using ENCAS and separate training of supernetworks
(see Section 6 for further discussion).

###  4.6. Applying ENCAS to SOTA ImageNet models

ENCAS relies on the architectures discovered via supernetwork-based NAS.
However, using a supernetwork means that these architectures are necessarily
not very large. Because of this, NAS results are typically evaluated in the
context of a mobile phone setting, which is usually taken to mean $\leq 600$
MFLOPs.

However, nowadays there are hundreds of large well-performing ImageNet-
pretrained models available online. Can our good results be extended from the
mobile phone setting to dominating the complete trade-off front? To answer
this question, we take 518 ImageNet models from the Pytorch Image Models
(timm) (Wightman, 2019) library, and run our search procedure on them.

Figure 8. ENCAS discovers a dominating trade-off front on ImageNet by
searching for cascades of 518 timm models (from which only the models on the
trade-off front are shown).

As shown in Figure 8, this indeed leads to a dominating trade-off front. The
increase of 0.4 percentage points in the maximum ImageNet performance leads to
our largest cascade achieving the highest ImageNet accuracy of publicly
available models (89.01±0.10), while simultaneously decreasing FLOPs by 18%
(from 362 GFLOPs to 296±77 GFLOPs). Our cascades outperform those in (Wang et
al., 2020), in large part thanks to the ability of our algorithm to use a
search space containing hundreds of models, which is not feasible for the
exhaustive search approach used in (Wang et al., 2020).

##  5\. Additional experiments

In this section we further investigate the impact of using more than one
supernetwork. Due to space constraints, a comparison to ensembles is provided
in Appendix B and a comparison to random search is provided in Appendix C.

###  5.1. Impact of increasing the number of supernetworks

Figure 9 shows the impact of increasing the number of supernetworks used in
ENCAS from 1 to 2 to 5. A trend of increasing hypervolume can be clearly
observed.

For joint training (ENCAS-joint), the hypervolume also increases, but not as
much. This can be explained by the increase in the search space that every
additional supernetwork brings. Interestingly, the hypervolume obtained with
ENCAS-joint+ grows about as fast as with ENCAS, which we interpret to mean
that the joint training and search over an increasing number of supernetworks
is beneficial for weights while harmful for the simultaneous search (given the
same search budget). The larger search space may require a larger search
budget to achieve better results, and therefore ENCAS-joint may have higher
potential to benefit from more compute. Running ENCAS using the weights
trained by ENCAS-joint (i.e. ENCAS-joint+) realizes the benefit of better
weights and ameliorates the downside of a larger search space.

(a) CIFAR-10

(b) CIFAR-100

Figure 9. Impact of increasing the number of supernetworks in ENCAS, ENCAS-
joint, ENCAS-joint+.

###  5.2. Is using different supernetworks better than using the best one
trained several times?

Experiments in section 4.3 demonstrated that using several supernetworks is
better than using just the best one. But is the source of the effect the
diversities of architectures found, or just the increased quantity of networks
with different weights? To answer this question, we train (via NAT) the best
supernetwork 5 times with different seeds on CIFAR-10 and CIFAR-100 and apply
ENCAS to the resulting trade-off fronts.

Figure 10. Comparison between hypervolume when using different supernetworks,
or the best supernetwork trained with different seeds on (top left) CIFAR-10,
(bottom left) CIFAR-100. (right) shows comparison between trade-off fronts of
5 supernetworks, or 5 seeds of the best supernetwork on CIFAR-10.

In Fig. 10 (left) we see that using different runs of the best supernetwork
barely increases hypervolume, in contrast to using different supernetworks. If
we inspect the trade-off fronts in Fig. 10 (right) for 5 supernetworks and for
5 seeds of the best supernetwork on CIFAR-10, we can see that the difference
is in low-FLOPs models that are missing from the best supernetwork but are
present in other supernetworks. Therefore, using diverse supernetworks is
helpful for obtaining a larger trade-off front coverage. However, on the side
of the most accurate networks, using multiple restarts of NAT with the best
supernetwork is sufficient to get close to the best performance, unlike what
could be expected, since the diversity in architectures and weights is
arguably lower.

##  6\. Discussion

While our approach achieves good results with limited resource usage, it still
suffers from limitations. Notably, it relies on pretrained supernetworks,
which are currently not very diverse, architecture-wise. Additionally, these
supernetworks need to allow extraction and usage of subnetworks without
retraining in order for our approach to work, which limits their selection
even further.

In our experiments, we find that performing search after the supernetwork
weights have been adapted is not much worse than joint training and search.
This can mean that there is not a lot of benefit to be gained by fine-tuning
architecture choices of different cascade components to each other;
alternatively, perhaps ENCAS-joint was simply not able to realize these
benefits, for instance because it may require more computational resources
than we used in our experiments.

This paper has demonstrated the benefits brought by the usage of cascades.
This reinforces the main thesis of (Wang et al., 2020): researchers should pay
more attention to cascades. However, the warnings of (Wang et al., 2020)
should also be repeated, as they apply to any cascade approach, including
ours: the decrease in FLOPs brought by cascades can be realized either when
processing images one-by-one, or when processing a large amount of images
offline. The benefits are not realized in online batch processing: once a
batch has been created, due to the parallel nature of GPU accelerators,
processing a part of a batch takes approximately the same resources as
processing the whole batch.

##  7\. Conclusion

In this paper, we considered the automatic creation of cascades of deep neural
networks. We developed an effective algorithm called ENCAS that builds upon
the literature on efficient NAS by searching for cascades across pretrained
supernetworks either simultaneously with weight training or after weight
training. ENCAS is the first NAS algorithm that searches for cascade
architectures. It does so by solving the multi-objective optimization problem
of finding well-performing small cascades with the help of an EA (MO-GOMEA).

ENCAS was found to outperform SOTA efficient NAS approaches on several image
classification datasets. Its search procedure can also be applied to an
arbitrary model pool. By applying it to well-performing publicly available
ImageNet models, we achieved a dominating trade-off front on ImageNet.

Finally, we find that searching for neural network architectures in more than
one pretrained supernetwork is beneficial despite the limited diversity of the
currently available supernetworks, which is expected to only increase with
time.

###### Acknowledgements.

We thank Arkadiy Dushatskiy for insightful discussions, Marco Virgolin for
introducing us to (Wang et al., 2020), Zhichao Lu for sharing his knowledge
about NAT and parts of the NAT codebase. This work is part of the research
project DAEDALUS funded via the Open Technology Programme of the Netherlands
Organization for Scientific Research (NWO), project number 18373; part of the
funding is provided by Elekta and ORTEC LogiqCare. This work was carried out
(in part) on the Dutch national e-infrastructure with the support of SURF
Cooperative.

## References

  * (1)
  * Angelova et al. (2015) Anelia Angelova, Alex Krizhevsky, Vincent Vanhoucke, Abhijit Ogale, and Dave Ferguson. 2015\.  Real-Time Pedestrian Detection With Deep Network Cascades. In _Proceedings of BMVC 2015_.
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014\.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ (2014).
  * Baker et al. (2017) Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. 2017.  Accelerating neural architecture search using performance prediction.  _arXiv preprint arXiv:1705.10823_ (2017).
  * Blank et al. (2020) J. Blank, K. Deb, Y. Dhebar, S. Bandaru, and H. Seada. 2020.  Generating Well-Spaced Points on a Unit Simplex for Evolutionary Many-Objective Optimization.  _IEEE Transactions on Evolutionary Computation_ 25, 1 (2020), 48–60.
  * Bouter et al. (2019) Anton Bouter, Tanja Alderliesten, Bradley R Pieters, Arjan Bel, Yury Niatsetski, and Peter A N Bosman. 2019.  GPU-accelerated bi-objective treatment planning for prostate high-dose-rate brachytherapy.  _Medical Physics_ 46, 9 (2019), 3776–3787.
  * Branke and Schmeck (2003) Jürgen Branke and Hartmut Schmeck. 2003.  Designing evolutionary algorithms for dynamic optimization problems.  In _Advances in Evolutionary Computing_. Springer, 239–262.
  * Broomhead and Lowe (1988) David S Broomhead and David Lowe. 1988.  _Radial basis functions, multi-variable functional interpolation and adaptive networks_.  Technical Report. Royal Signals and Radar Establishment Malvern (United Kingdom).
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in Neural Information Processing Systems_ 33 (2020), 1877–1901.
  * Cai et al. (2020) Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. 2020.  Once for All: Train One Network and Specialize it for Efficient Deployment. In _International Conference on Learning Representations_.
  * Cai et al. (2019) Han Cai, Ligeng Zhu, and Song Han. 2019.  ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=HylVB3AqYm
  * Cai et al. (2015) Zhaowei Cai, Mohammad Saberian, and Nuno Vasconcelos. 2015\.  Learning complexity-aware cascades for deep pedestrian detection. In _Proceedings of the IEEE International Conference on Computer Vision_. 3361–3369.
  * Chen et al. (2021) Minghao Chen, Jianlong Fu, and Haibin Ling. 2021.  One-Shot Neural Ensemble Architecture Search by Diversity-Guided Search Space Shrinking. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 16530–16539.
  * Chiong et al. (2012) Raymond Chiong, Thomas Weise, and Zbigniew Michalewicz. 2012\.  _Variants of evolutionary algorithms for real-world applications_.  Springer.
  * Cubuk et al. (2020) Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. 2020\.  RandAugment: Practical automated data augmentation with a reduced search space. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_. 702–703.
  * Das and Dennis (1998) Indraneel Das and John E Dennis. 1998.  Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems.  _SIAM Journal on Optimization_ 8, 3 (1998), 631–657.
  * Deb and Jain (2013) Kalyanmoy Deb and Himanshu Jain. 2013.  An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints.  _IEEE Transactions on Evolutionary Computation_ 18, 4 (2013), 577–601.
  * DeVries and Taylor (2017) Terrance DeVries and Graham W Taylor. 2017.  Improved regularization of convolutional neural networks with cutout.  _arXiv preprint arXiv:1708.04552_ (2017).
  * Donahue et al. (2014) Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. 2014.  Decaf: A deep convolutional activation feature for generic visual recognition. In _International Conference on Machine Learning_. PMLR, 647–655.
  * Dong and Yang (2019a) Xuanyi Dong and Yi Yang. 2019a.  One-shot neural architecture search via self-evaluated template network. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 3681–3690.
  * Dong and Yang (2019b) Xuanyi Dong and Yi Yang. 2019b.  Searching for a robust neural architecture in four gpu hours. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 1761–1770.
  * Dunn (1961) Olive Jean Dunn. 1961\.  Multiple comparisons among means.  _J. Amer. Statist. Assoc._ 56, 293 (1961), 52–64.
  * Esposito and Saitta (2003) Roberto Esposito and Lorenza Saitta. 2003.  Monte Carlo theory as an explanation of bagging and boosting. In _IJCAI_ , Vol. 3. 499–504.
  * Howard et al. (2019) Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. 2019\.  Searching for MobileNetv3. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 1314–1324.
  * Isensee et al. (2021) Fabian Isensee, Paul F Jaeger, Simon AA Kohl, Jens Petersen, and Klaus H Maier-Hein. 2021.  nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation.  _Nature methods_ 18, 2 (2021), 203–211.
  * Izmailov et al. (2018) Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. 2018\.  Averaging weights leads to wider optima and better generalization. In _34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018_. Association For Uncertainty in Artificial Intelligence, 876–885.
  * Kornblith et al. (2019) Simon Kornblith, Jonathon Shlens, and Quoc V Le. 2019.  Do better ImageNet models transfer better?. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 2661–2671.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al. 2009\.  _Learning multiple layers of features from tiny images_.  Technical Report.
  * Kukenys and McCane (2008) Ignas Kukenys and Brendan McCane. 2008.  Classifier cascades for support vector machines. In _2008 23rd International Conference Image and Vision Computing New Zealand_. IEEE, 1–6.
  * LeCun et al. (1995) Yann LeCun, Yoshua Bengio, et al. 1995\.  Convolutional networks for images, speech, and time series.  _The handbook of brain theory and neural networks_ 3361, 10 (1995), 1995.
  * Li and Talwalkar (2020) Liam Li and Ameet Talwalkar. 2020.  Random Search and Reproducibility for Neural Architecture Search. In _Proceedings of The 35th Uncertainty in Artificial Intelligence Conference_ _(Proceedings of Machine Learning Research, Vol. 115)_ , Ryan P. Adams and Vibhav Gogate (Eds.). PMLR, 367–377.  https://proceedings.mlr.press/v115/li20c.html
  * Liu et al. (2018) Hanxiao Liu, Karen Simonyan, and Yiming Yang. 2018\.  DARTS: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ (2018).
  * Loshchilov and Hutter (2016) Ilya Loshchilov and Frank Hutter. 2016.  SGDR: Stochastic gradient descent with warm restarts.  _arXiv preprint arXiv:1608.03983_ (2016).
  * Lu et al. (2020) Zhichao Lu, Kalyanmoy Deb, Erik Goodman, Wolfgang Banzhaf, and Vishnu Naresh Boddeti. 2020\.  NSGANetv2: Evolutionary multi-objective surrogate-assisted neural architecture search. In _European Conference on Computer Vision_. Springer, 35–51.
  * Lu et al. (2021) Zhichao Lu, Gautam Sreekumar, Erik Goodman, Wolfgang Banzhaf, Kalyanmoy Deb, and Vishnu Naresh Boddeti. 2021.  Neural architecture transfer.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 43, 9 (2021), 2971–2989.
  * Luong et al. (2015) Ngoc Hoang Luong, Marinus OW Grond, Han La Poutré, and Peter A N Bosman. 2015.  Scalable and practical multi-objective distribution network expansion planning. In _2015 IEEE Power & Energy Society General Meeting_. IEEE, 1–5.
  * Luong et al. (2014) Ngoc Hoang Luong, Han La Poutré, and Peter A N Bosman. 2014\.  Multi-objective gene-pool optimal mixing evolutionary algorithms. In _Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation_. 357–364.
  * Narayanan et al. (2021) Ashwin Raaghav Narayanan, Arber Zela, Tonmoy Saikia, Thomas Brox, and Frank Hutter. 2021\.  Multi-headed Neural Ensemble Search. In _Workshop on Uncertainty and Robustness in Deep Learning (UDL@ICML‘21)_.
  * Nesterov (1983) Yurii E Nesterov. 1983\.  A method for solving the convex programming problem with convergence rate O (1/$k^{2}$). In _Dokl. akad. nauk SSSR_ , Vol. 269. 543–547.
  * Petchrompo et al. (2022) Sanyapong Petchrompo, Anupong Wannakrairot, and Ajith Kumar Parlikad. 2022.  Pruning pareto optimal solutions for multi-objective portfolio asset management.  _European Journal of Operational Research_ 297, 1 (2022), 203–220.
  * Pham et al. (2018) Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. 2018.  Efficient neural architecture search via parameters sharing. In _International Conference on Machine Learning_. PMLR, 4095–4104.
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. 2019.  Regularized evolution for image classifier architecture search. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 4780–4789.
  * Recht et al. (2019) Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. 2019.  Do ImageNet classifiers generalize to ImageNet?. In _International Conference on Machine Learning_. PMLR, 5389–5400.
  * Rodrigues et al. (2016) S Rodrigues, Pavol Bauer, and Peter A N Bosman. 2016.  Multi-objective optimization of wind farm layouts–Complexity, constraint handling and scalability.  _Renewable and Sustainable Energy Reviews_ 65 (2016), 587–609.
  * Rokach (2010) Lior Rokach. 2010\.  Ensemble-based classifiers.  _Artificial Intelligence Review_ 33, 1 (2010), 1–39.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. 2015\.  ImageNet large scale visual recognition challenge.  _International Journal of Computer Vision_ 115, 3 (2015), 211–252.
  * Sandler et al. (2018) Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. 2018.  MobileNetv2: Inverted residuals and linear bottlenecks. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 4510–4520.
  * Sharma et al. (2020) Rishab Sharma, Rahul Deora, and Anirudha Vishvakarma. 2020\.  AlphaNet: An Attention Guided Deep Network for Automatic Image Matting. In _2020 International Conference on Omni-layer Intelligent Systems_. IEEE, 1–8.
  * Shu et al. (2021) Yao Shu, Yizhou Chen, Zhongxiang Dai, and Bryan Kian Hsiang Low. 2021.  Going Beyond Neural Architecture Search with Sampling-based Neural Ensemble Search.  _arXiv preprint arXiv:2109.02533_ (2021).
  * Singh and Deb (2006) Gulshan Singh and Kalyanmoy Deb. 2006.  Comparison of multi-modal optimization algorithms based on evolutionary algorithms. In _Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation_. 1305–1312.
  * Stamoulis et al. (2019) Dimitrios Stamoulis, Ruizhou Ding, Di Wang, Dimitrios Lymberopoulos, Bodhi Priyantha, Jie Liu, and Diana Marculescu. 2019\.  Single-path NAS: Designing hardware-efficient convnets in less than 4 hours.  _arXiv preprint arXiv:1904.02877_ (2019).
  * Streeter (2018) Matthew Streeter. 2018\.  Approximation algorithms for cascading prediction models. In _International Conference on Machine Learning_. PMLR, 4752–4760.
  * Tan and Le (2019) Mingxing Tan and Quoc Le. 2019.  EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. In _Proceedings of the 36th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 97)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 6105–6114.  https://proceedings.mlr.press/v97/tan19a.html
  * Thierens and Bosman (2011) Dirk Thierens and Peter A N Bosman. 2011.  Optimal mixing evolutionary algorithms. In _Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation_. 617–624.
  * Van Veldhuizen and Lamont (1998) David A Van Veldhuizen and Gary B Lamont. 1998.  _Multiobjective evolutionary algorithm research: A history and analysis_.  Technical Report. Citeseer.
  * Viola and Jones (2001) Paul Viola and Michael Jones. 2001.  Rapid object detection using a boosted cascade of simple features. In _Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , Vol. 1. IEEE, I–I.
  * Wang et al. (2021) Dilin Wang, Meng Li, Chengyue Gong, and Vikas Chandra. 2021\.  AttentiveNAS: Improving neural architecture search via attentive sampling. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 6418–6427.
  * Wang et al. (2020) Xiaofang Wang, Dan Kondratyuk, Kris M Kitani, Yair Movshovitz-Attias, and Elad Eban. 2020\.  Multiple networks are more efficient than one: Fast and accurate models via ensembles and cascades.  _arXiv preprint arXiv:2012.01988_ (2020).
  * White et al. (2021) Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. 2021.  How Powerful are Performance Predictors in Neural Architecture Search?. In _Advances in Neural Information Processing Systems_ , Vol. 34. 28454–28469.
  * Wichard et al. (2003) Jörg Wichard, Christian Merkwirth, and Maciej Ogorzalek. 2003.  Building ensembles with heterogeneous models.  (2003).
  * Wightman (2019) Ross Wightman. 2019\.  PyTorch Image Models.  https://github.com/rwightman/pytorch-image-models.  https://doi.org/10.5281/zenodo.4414861
  * Wilcoxon (1992) Frank Wilcoxon. 1992\.  Individual comparisons by ranking methods.  In _Breakthroughs in statistics_. Springer, 196–202.
  * Xu et al. (2014) Zhixiang Xu, Matt J Kusner, Kilian Q Weinberger, Minmin Chen, and Olivier Chapelle. 2014\.  Classifier cascades and trees for minimizing feature evaluation cost.  _The Journal of Machine Learning Research_ 15, 1 (2014), 2113–2144.
  * Yu et al. (2020) Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le. 2020\.  BigNAS: Scaling up neural architecture search with big single-stage models. In _European Conference on Computer Vision_. Springer, 702–717.
  * Yun et al. (2019) Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. 2019\.  CutMix: Regularization strategy to train strong classifiers with localizable features. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 6023–6032.
  * Zaidi et al. (2021) Sheheryar Zaidi, Arber Zela, Thomas Elsken, Christopher C. Holmes, Frank Hutter, and Yee Whye Teh. 2021.  Neural Ensemble Search for Uncertainty Estimation and Dataset Shift. In _Thirty-Fifth Conference on Neural Information Processing Systems_.
  * Zitzler et al. (2003) Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M Fonseca, and Viviane Grunert Da Fonseca. 2003\.  Performance assessment of multiobjective optimizers: An analysis and review.  _IEEE Transactions on Evolutionary Computation_ 7, 2 (2003), 117–132.
  * Zoph and Le (2016) Barret Zoph and Quoc V Le. 2016.  Neural architecture search with reinforcement learning.  _arXiv preprint arXiv:1611.01578_ (2016).

## APPENDIX

##  Appendix A Hyperparameters

In this section, hyperparameters for our experiments are listed.

Reproducing NAT: initial learning rate 0.01, optimizer Stochastic Gradient
Descent with Nesterov momentum 0.9 (Nesterov, 1983), training for 30 meta-
iteration of 5 epochs each, cosine learning rate schedule (Loshchilov and
Hutter, 2016), train batch size 96, validation batch size 150, CutOut (DeVries
and Taylor, 2017) with size 56, RandAugment (Cubuk et al., 2020) with the
policy ”rand-m9-mstd0.5”, 10,000 surrogate evaluations for each meta-
iteration, the surrogate is an ensemble of 500 RBFs (Broomhead and Lowe,
1988), archive size 300, sampling a network to train by constructing a
distribution of possible architecture choices from archive and sampling each
choice from this distribution.

Better NAT results (only differences are listed): cosine cyclic learning rate
schedule with period of 5 epochs, CutOut is replaced with CutMix (Yun et al.,
2019), Stochastic Weight Averaging (Izmailov et al., 2018) of models from the
last 20 meta-iterations (i.e. epochs 150, 145,.. 55), sampling a network to
train by directly sampling an architecture from the archive.

ENCAS-joint: 5 epochs per supernetwork per iteration, the rest follows ”Better
NAT results”.

Techniques suggested to us privately by the NAT authors to improve NAT
performance are: usage of CutOut, RandAugment, and Riesz s-energy (Blank et
al., 2020) for reference point generation instead of the Das-Dennis method
(Das and Dennis, 1998).

ENCAS was run for 600,000 evaluations. For experiments with timm an Nvidia
A100 card was used for its superior VRAM size.

##  Appendix B Evolutionary Neural Ensemble Search

In this section we briefly discuss a restriction of ENCAS to ensemble search,
an algorithm we name Evolutionary Neural ENsemble Search (ENENS). Whereas
ENCAS searches for a sequence of models and confidence thresholds, ENENS
searches only for the models, as confidence thresholds are not needed in an
ensemble. The overall procedure is a simplified version of the one in ENCAS
(Section 3.1): a solution representation consists of model indices (thresholds
are no longer a part of the representation); a solution is evaluated by
averaging the predictions of all the models in it; the FLOPs count is the sum
of FLOPs counts of all the models in the ensemble. The rest of the algorithm
is unchanged.

###  B.1. Comparison with existing Neural Ensemble Search algorithms

The existing algorithms for ensemble architecture search do not use pretrained
supernetworks. Being able to use pretrained supernetworks is an important
advantage in deep learning, an advantage that is realized by ENENS, which can
be seen to exhibit superior performance in terms of top-1 accuracy, as
reported in Table 4.

Table 4. Top-1 accuracy of different algorithms for search of network architectures for an ensemble. For our experiment, mean and standard deviation across 10 seeds are reported. Method | CIFAR-10 | CIFAR-100 | ImageNet
---|---|---|---
NES (Zaidi et al., 2021) | 92.4 | 76.5 | —
MH-NES (Narayanan et al., 2021) | — | 80.35 | —
NESS (Shu et al., 2021) | 97.64 | 85.45 | 77.7
NEAS (Chen et al., 2021) | — | — | 80.0
ENENS | 98.62±0.06 | 88.99±0.09 | 82.80±0.07

###  B.2. Cascade vs ensemble

The comparison of ENCAS and ENENS in Figure 11 shows that the front of
cascades dominates for most FLOPs values. The largest ensembles perform very
similarly, or, in case of ImageNet, perhaps perform slightly better, even
though technically they could be found by ENCAS as special cases of cascades.
Best we can tell, this does not happen because in the largest-FLOPs regime
ENCAS finds smaller cascades and ensembles (than ENENS) that perform better on
the validation set, but lose a bit of performance on the test set. The larger
ensembles found by ENENS do not face this issue. The small increase in
accuracy comes at the cost of thousands more MFLOPs, however, which means that
ensembles should be considered only when efficiency is of no concern.

(a) CIFAR-10

(b) CIFAR-100

(c) ImageNet

Figure 11. The trade-off front of cascades is better than the trade-off front
of ensembles on the test set.

##  Appendix C Comparison to random search

(a) CIFAR-10

(b) CIFAR-100

(c) ImageNet

Figure 12. MO-GOMEA outperforms random search in terms of hypervolume of the
validation trade-off fronts.

Random search is a strong baseline for NAS (Li and Talwalkar, 2020).
Consequently, we replace MO-GOMEA in ENCAS with random search to investigate
whether a simpler search algorithm will suffice. In Fig. 12 we can see that
while random search achieves better results in the first several hundred
evaluations of search, it is overtaken by MO-GOMEA after that, demonstrating
the benefit of the more sophisticated search approach in terms of the
optimization problem it is tasked to solve.

Table 5. Comparison of using MO-GOMEA and random search in ENCAS (test set performance, mean and standard deviation are computed across 10 seeds) Method |  Hypervolume |  Max accuracy |  Max MFLOPs
---|---|---|---
CIFAR-10
Random | 0.941±0.002 | 98.61±0.08 | 814±307
MO-GOMEA | 0.941±0.002 | 98.60±0.09 | 749±298
CIFAR-100
Random | 0.698±0.003 | 88.91±0.15 | 1298±389
MO-GOMEA | 0.699±0.003 | 88.96±0.17 | 1401±420
ImageNet
Random | 0.535±0.001 | 82.66±0.07 | 2708±588
MO-GOMEA | 0.537±0.001 | 82.72±0.10 | 2614±221

However, Table 5 shows that the difference in test performance over all the
datasets is small (not statistically significant). Better performance of MO-
GOMEA on the validation set but not the test set means that overfitting to the
validation set occurs. Combatting overfitting is an avenue for future work.

##  Appendix D ENCAS models for reference

In the main text we avoid naming specific models on the trade-off front, as we
believe that it is helpful to have NAS produce tens or hundreds of models that
may differ only slightly but that allow users more flexibility in choosing
which one to use. Nonetheless, to make referencing our models easier, here we
specify FLOPs and top-1 accuracy of selected models. A model is included if
its MFLOPs value is closest to a value divisible by 100 — this way we select a
representative and spread-out sample of the trade-off front while avoiding
cherry-picking. The models are taken from the median run (by hypervolume as
evaluated on the test set).

Table 6. CIFAR-10, selected models Name | MFLOPs | Accuracy
---|---|---
ENCAS@100 | 100 | 96.19
ENCAS@186 | 186 | 98.23
ENCAS@276 | 276 | 98.49
ENCAS@439 | 439 | 98.57
Table 7. CIFAR-100, selected models Name | MFLOPs | Accuracy
---|---|---
ENCAS@100 | 100 | 78.98
ENCAS@202 | 202 | 85.85
ENCAS@299 | 299 | 87.14
ENCAS@405 | 405 | 88.08
ENCAS@503 | 503 | 88.26
ENCAS@607 | 607 | 88.42
ENCAS@694 | 694 | 88.42
ENCAS@865 | 865 | 88.88
ENCAS@1217 | 1217 | 88.57
ENCAS@1330 | 1330 | 88.98
ENCAS@2419 | 2419 | 88.95
Table 8. ImageNet, selected models Name | MFLOPs | Accuracy
---|---|---
ENCAS@100 | 100 | 68.19
ENCAS@211 | 211 | 77.75
ENCAS@301 | 301 | 79.74
ENCAS@387 | 387 | 80.43
ENCAS@517 | 517 | 80.79
ENCAS@615 | 615 | 81.34
ENCAS@690 | 690 | 81.49
ENCAS@817 | 817 | 81.87
ENCAS@900 | 900 | 82.11
ENCAS@1006 | 1006 | 82.14
ENCAS@1060 | 1060 | 82.20
ENCAS@1160 | 1160 | 82.36
ENCAS@1357 | 1357 | 82.49
ENCAS@1559 | 1559 | 82.63
ENCAS@1687 | 1687 | 82.66
ENCAS@2526 | 2526 | 82.71

##  Appendix E Statistical testing

Table 9 lists p-values for one-sided Wilcoxon pairwise rank tests with
Bonferroni correction (null hypothesis is that Algorithm 1 is worse than
Algorithm 2).

All benchmark datasets (CIFAR-10, CIFAR-100, ImageNet) are tested together to
increase sample size. P-values below a significance threshold of 0.0005 are
highlighted (target $p$-value=0.01, 20 tests, corrected $p$=0.0005). P-values
are rounded for visualization purposes. Unless specified otherwise, 5
supernetworks are used. Experiments are separated into two groups: those in
the main text and those in the appendix.

Table 9. P-values of conducted experiments Algorithm 1 | Algorithm 2 | Split | Hypervolume | Max accuracy
---|---|---|---|---
ENCAS (1 supernetwork) | NAT (best) | test | 5.6e-6 | 0.0008
ENCAS | NAT (best) | test | 8.7e-7 | 8.7e-7
ENCAS | ENCAS (1 supernetwork) | test | 8.7e-7 | 8.7e-7
ENCAS | GreedyCascade | test | 8.7e-7 | 8.7e-7
ENCAS-joint+ | ENCAS-joint | test | 1.9e-6 | 0.0008
ENCAS-joint+ | ENCAS | test | 0.0133 | 0.0093
ENCAS | ENCAS (5 seeds of the best supernet) | test | 9.5e-7 | 0.9385
ENCAS | ENENS | test | 8.7e-7 | 0.9829
ENCAS with MO-GOMEA | ENCAS with Random search | val | 8.7e-7 | 1.8e-6
ENCAS with MO-GOMEA | ENCAS with Random search | test | 0.0247 | 0.0512

##  Appendix F Hypervolume

Figure 13. Hypervolume indicator for the task of maximizing accuracy and
minimizing FLOPs

The hypervolume indicator measures the volume encapsulated between the trade-
off front and a reference point in the objective space (Zitzler et al., 2003).
Hypervolume is a useful metric of the quality of a trade-off front.

Since hypervolume is measured relative to a reference point, its absolute
value has no meaning, as changing the reference point changes it. However, if
the reference point is fixed, relative differences between the hypervolumes of
different algorithms can indicate which of them finds a better trade-off
front. Note however that hypervolume, while useful, does not perfectly catch
every aspect that is important when comparing fronts. Especially when values
are close, other measures or visual front inspection are advised.

A visual representation of hypervolume can be seen in Fig. 13. Normalized
hypervolume means hypervolume divided by its largest possible value. In our
experiments the reference point is fixed at (MFLOPs=$4000$, accuracy=$60$).