Neural Ensemble Search for Uncertainty Estimation and Dataset Shift
Authors: Sheheryar Zaidi
Arber Zela
Thomas Elsken
Chris Holmes
Frank Hutter
Yee Whye Teh
Venue:  (2021)
Keywords: uncertainty estimation
deep ensemble
dataset shift
robustness
uncertainty calibration

Abstract: Ensembles of neural networks achieve superior performance compared to stand-alone networks not only in terms of predictive performance, but also uncertainty calibration and robustness to dataset shift. Diversity among networks is believed to be key for building strong ensembles, but typical approaches, such as \emph{deep ensembles}, only ensemble different weight vectors of a fixed architecture. Instead, we propose two methods for constructing ensembles to exploit diversity among networks with \emph{varying} architectures. We find that the resulting ensembles are indeed more diverse and also exhibit better uncertainty calibration, predictive performance and robustness to dataset shift in comparison with deep ensembles on a variety of classification tasks.

Under review as a conference paper at ICLR 2021
NEURAL ENSEMBLE SEARCH FOR UNCERTAINTY ESTIMATION AND DATASET SHIFT
Anonymous authors Paper under double-blind review
ABSTRACT
Ensembles neural networks achieve superior performance compared to stand- alone networks not only in terms of predictive performance, but also uncertainty calibration and robustness to dataset shift. Diversity among networks is believed to be key for building strong ensembles, but typical approaches, such as deep ensembles, only ensemble different weight vectors of fixed architecture. Instead, we propose two methods for constructing ensembles exploit diversity among networks with varying architectures. We find the resulting ensembles are indeed more diverse and also exhibit better uncertainty calibration, predictive performance and robustness to dataset shift in comparison with deep ensembles on a variety of classification tasks.
INTRODUCTION
Automatically learning useful representations of data using deep neural networks has been successful across various tasks (Krizhevsky et al. 2012: Hinton et al. 2012 Mikolov et al. 2013). While some applications rely only on the predictions made by a neural network, many critical applications also require reliable predictive uncertainty estimates and robustness under the presence of dataset shift, that is, when the observed data distribution at deployment differs from the training data distribution. Examples include medical imaging (Esteva et al., (017)) and self-driving cars (Bojarski et al. (016). However, several studies have shown that neural networks
not always robust to dataset shift (Ovadia et al. 2019; Hendryycks & Dietterich, 2019). nor do they exhibit calibrated predictive uncertainty, resulting in incorrect predictions made with high confidence (Guo et al.) 2017).
Using an ensemble of networks rather than a stand-alone network improves both predictive uncer- tainty calibration and robustness dataset shift. Ensembles also outperform approximate Bayesian methods (Lakshminarayanan et al. [2017] Ovadia et al. 2019 Gustafsson et al. 2020). Their success usually attributed the diversity among the base learners, however there are various definitions of diversity (Kuncheva & Whitaker 2003 Zhou 2012) without a consensus. In practice, ensembles are usually constructed by choosing fixed state-of-the-an architecture and creating base learn- ers by independently training random initializations of it. This is referred to as deep ensembles (I lakshminarayanan et al. 2017), state-of-the-art method for uncertainty estimation.
However, as we show, base learners with varying network architectures make more diverse predictions. Therefore, picking a strong, fixed architecture for the ensemble's base learners neglects diversity in favor of base learner strength. This has implications for the ensemble performance, since both diversity and base learner strength are important. To overcome this, we propose Neural Ensemble Search (NES); NES algorithm finds set of diverse neural architectures that together form a strong ensemble. Note that, a priori. it is not obvious how to find diverse architectures that work well as an ensemble; one cannot randomly select them, since it is important select strong ones, nor can one optimize them individually as that ignores diversity. By directly optimizing ensemble loss while maintaining independent training base learners, NES algorithm implicitly encourages diversity, without the need for explicitly defining diversity. In detail, our contributions are as follows:
1. We show that ensembles composed of varying architectures perform better than ensembles composed of a fixed architecture. We demonstrate that this due to increased diversity among the ensemble's 's base learners (Sections 3 and 5

---

Under review as a conference paper at ICLR 2021
2. Based on these findings and the importance of diversity, propose two algorithms for Neural Ensemble Search: NES-RS and NÈS-RE. RE. NES-RS is a simple random search based algorithm. and NES-RE is based on regularized evolution (Real et al. 2019). Both search algorithms seek performant ensembles with varying base learner architectures (Section
With experiments on classification tasks, we evaluate the ensembles found by NES-RS and NES- RE from the point of view of both predictive performance and uncertainty calibration, comparing them to deep ensembles with fixed, optimized architectures. We find our ensembles outperform deep ensembles not only on in-distribution data but also during dataset shift (Section 5p. The code for our experiments is available at: https:/ hetp:///nnnymouuuee iomooussfilee fils.. io/2aYlcc25)
RELATED WORK
Ensemble Learning and Uncertainty Estimation. Ensembles of neural networks (Hansen & Salamon 1990 Krogh& & Vedelsby 1995 Dietterich] 2000) are commonly used to boost performance
(Szegedy et al. 2015 (Simonyan & Zisserman 2015| He et al.] (016). In practice, strategies for building ensembles include the popular approach of independently training multiple initializations of the same network (i.e. deep ensembles (Lakshminarayanan
al.) (017)), training base learners on bootstrap samples of the training data (i.e. bagging) (Zhou et al. 2002), joint training with diversity-encouraginn
losses (Liu & Yao 1999] Lee et al. 2015: Zhou et al. 2018: Webb al.) 2019 Jain et al. 2020 Pearce et (0020) and using checkpoints during the training trajectory of network (Huang et al. Loshchilo & Hutter 2017). Much recent interest in ensembles has been due to their strong predictive uncertainty estimation, with extensive empirical studies (Ovadia et al.) 2019; Gustafsson et al.) 2020) observing that ensembles outperform other approaches for uncertainty estimation, notably including Bayesian methods (Gal & Ghahramani 2016 Welling & Teh 2011) and post-hoc calibration (Guo et al., 2017). Note He et al. (2020) draw a link between Bayesian methods and deep ensembles. We focus on deep ensembles they provide state-of offte--f--heaarr results in uncertainty estimation. Note that Ashukha et al. (2020) found many sophisticated ensembling techniques to be equivalent small-sized deep ensemble in terms of test performance.
Auto.M.. AutoML (Hutter et al. 2018 is the process of automatically designing machine learning systems. Automatic ensemble construction commonly used in AutoML (Feurer et al.. 2015). Lévesque et al. (2016) use Bayesian optimization to tune non-architectural hyperparameters of an ensemble's base learners, relying ensemble selection (Caruana et al., 2004). Specific to neural networks, AutoML also includes neural architecture search (NAS), the process of automatically designing network architectures (Elsken et al.) 2019). Existing strategies using reinforcement learn- ing (Zoph & Le 2017), evolutionary algorithms (Real et al.) 2019) or gradient-basee based methods (Liu ct al. 2019) have demonstrated that NAS can find architectures that surpass hand-crafted ones.
Some recent research connects ensemble learning with NAS. Methods proposed by Cortes et al. (001)) and Macko et al. (2019) iteratively add (sut-)networrs to an ensemble to improve the ensemble's performance. While our work focuses on generating a diverse and well-performing (in an ensemble) set of architectures while fixing how the ensemble is built from its base learners, the aforementioned works focus on how to build the ensemble. The search spaces considered by these works are also limited compared to ours: Cortes et al. (2017) consider fully-connected layers and Macko et al. (2019) only use NASNet-A (Zoph al.) 2018) blocks with varying depth and number of filters. All aforementioned works only focus on predictive performance and do not consider uncertainty estimation and dataset shift. Concurrent to our work, Wenzel et al. (2020) consider ensembles with base learners having varying hyperparameters using an approach similar to NES-RS. However, they focus on non architectural hyperparameters such as Le regularization strength and dropout rates, keeping the architecture fixed. As in our work, they also consider predictive uncertainty calibration and robustness to shift, finding improvements over deep ensembles.
ENSEMBLES OF VARYING ARCHITECTURES ARE MORE DIVERSE
3.1 DEFINITIONS AND SET-UP
Let Dimin = [Z,, y:) : = N....,N} be the training dataset, where the input x; E RD and, assuming classification task, the output y/i (1,...,C) We use D and Disa for the validation
2

---

Under review as a conference paper at ICLR 2021
and test datasets, respectively. Denote by fo neural network with weights 8, fa(z) BC is the predicted probability vector over the classes for input x. Let ((fo(z). y) be the neural network's ss loss for data point (xt, y). Given M networks fo..... ......... fows we construct the ensemble F of these networks by averaging the outputs, yielding F(x:) = M ΣM (a).
In addition to the ensemble's 's loss ((F(z), y). we will also consider the average base learner loss and the oracle ensemble's 's loss. The average base learner loss is simply defined as 3t > i=1 f[fo, (æ), y): we use this to measure the average base learner strength. Similar to Lee et al. (2015); Zhou et al. defined be the function
(2018), the oracle ensemble For composed of base learners fo.....: fo which, given an imput æ, returns the prediction of the base learner with the smallest loss for (z, y). that is,
FOr(x) (2)),
where
k E argmin E(fe, (z).
Of course, the oracle ensemble can only be constructed if the true class is known. We use the oracle ensemble loss as a measure of the diversity in base learner predictions. Intuitively, if base learners make diverse predictions for æ, the oracle ensemble is more likely to find some base learner with a small loss, whereas if all base learners make identical predictions, the oracle ensemble yields the same output as any (and all) base learners. Therefore, as rule of thumb, small oracle ensemble loss indicates more diverse base learner predictions.
Proposition 3.1. Suppose is negative log-likelihood (NLL). Then, the oracle ensemble loss, ensemble loss, and average base learner loss satisfy the following inequality:
M
e( ((FOE()). S ((F())).))
(f).))))
M
We refer to Appendix for proof. Proposition 3.1 suggests that strong ensembles require not only strong average base learners (smaller upper bound), but also more diversity in their predictions (smaller lower bound). There is extensive theoretical work relating strong base learner performance and diversity with the generalization properties of ensembles (Hansen & Salamon 1990, Zhou 2012] Jiang et al. 2017: Bian Chen 2019 Goodfellow et al. (016)). Notably, Breiman (2001) showed that the generalization error of random forests depends on the strength of individual trees and the correlation between their mistakes.
3.2 VISUALIZING SIMILARITY IN BASE LEARNER PREDICTIONS
The fixed architecture used to build deep ensembles is typ- ically chosen to be a strong stand-alone architecture, either hand-crafted or found by NAS. However, since ensemble per- formance depends not only strong base learners but also on their diversity, optimizing the base learner's architecture and then constructing deep ensemble neglects diversity in favor of strong base learner performance.
MIL1
I-SNE dimension
Having base learner architectures vary allows more diversity in their predictions. In this section, we provide empirical evidence for this by visualizing the base learners' predictions. Fort et al. (019)) found that base learners in a deep ensemble explore different parts of the function space by means of applying di- mensionality reduction to their predictions. Building on this, we uniformly sample five architectures from the DART'S search space @Liu et al. 2019), train 20 initializations of each archi- tecture on CIFAR- 10 and visualize the similarity among the networks' predictions the test dataset using t-SNE (Van der
U-NE dimension
Figure I: t-SNE visualization: five different architectures, each trained with 20 different initializations.
Maaten & Hinton 2008). Experiment details are available in Section 5 and Appendix B
As shown in Figure we observe clustering of predictions made by different initializations of fixed architecture, suggesting that base learners with varying architectures explore different parts of the function space. Moreover, we also visualize the predictions of base learners of two ensembles, each
3

---

Under review as a conference paper at ICLR 2021
of size M = 30, where one is deep ensemble and the other has varying architectures (found by VES-RS which will be introduced in Section 4). varying architectures than in the deep ensemble. For each of the two ensembles shown in Figure [T] we also compute the average pairwise predictive disagreement amongst the base learners (percentage of test imputs on which two base learners disagree), which find be 11.88% for the ensemble with varying architectures and 10.51% for the ensemble with fixed architectures (this is consistent across independent runs). This indicates higher predictive diversity in the ensemble with varying architectures, in line with the t-SNE results.
more diversity in the ensemble with
4 NEURAL ENSEMBLE SEARCH
In this section, we introduce neural ensemble search (NES). In summary, a NES algorithm optimizes the architectures of base learners in an ensemble to minimize ensemble loss.
Given a network f TR - RC, let L(S D) = Eee.)DD (a)))) be the loss of f over dataset 'D. Given set of base learners [f,,... JM let Ensemble be the function which maps ....... fM} M 3 Σi= fi as defined in Section 3 To emphasize the architecture, we use the
to the ensemble notation fo.. to denote a network with architecture E A and weights 0, where A is a search space (SS) of architectures. A NES algorithm aims to solve the following optimization problem:
min L (eonsemble(Je..ap..... al..aa EA
Jos. Dea)
(1)
S.L. 0g E argmin L(Jo.an Darai) for = l,..., M
Eq. [ is difficult solve for at least two reasons. First, are optimizing over M architectures, so the search space is effectively AM, compared to it being A in typical NAS, making it more difficult to explore fully. Second, larger search space also increases the risk of overfitting the ensemble loss to D A possible approach here is to consider the ensemble as a single large network to which we apply NAS, but joint training of ensemble through single loss has been empirically observed to underperform training base learners independently, specially for large neural networks (Webb et al. 2019). Instead, our general approach to solve Eq. [ consists of two steps:
1. Pool building: build pool P = (Jor ........ Sex of size K consisting of potential base learners, where each fa, is a network trained independently on Dusin-
Ensemble selection: select M base learners foz .0 ......... for, from P form an ensemble which minimizes loss on a (We assume K 2 M.)
Step I reduces the options for the base learner architectures, with the intention to make the search more feasible and focus on strong architectures. Step 2 then selects performant ensemble which implicitly encourages base learner strength and diversity. This procedure also ensures that the ensemble's base learners
trained independently. We propose using forward step-wise selection for step 2: that is, given the set of networks P, we start with an empty ensemble and add to it the network from P which minimizes ensemble loss on Deal- We repeat this without replacement until the ensemble is of size M. Let ForwardSelect (P, Deats M) denote the set of M base learners selected from P by this procedure.
Note that selecting the ensemble from P is combinatorial optimization problem; a greedy approach nevertheless effective (Caruana et al. 2004), while keeping computational overhead low, given the predictions of the networks on D We also experimented with three other ensemble selection algorithms:
such as forwardSelesd
(1) Starting with the best network by validation performance, add the next best network to the ensemble only if it improves validation performance, iterating until the ensemble size is M or all models have been considered
(2) Select the top M networks by validation performance. (3) Forward step-wise wise selection with replacement. We typically found that these three performed comparatively or worse than our choice ForwardSelect.
We have not yet discussed the algorithm for building the pool in step 1; propose two approaches, NES-RS RS (Section 4 and NES- RE 4S.c NES-RS is simple random search based algorithm, while NES-RE is based regularized evolution (Real et al. 2019), ffte-oo-the--a NAS algorithm.
This approach returns an ensemble of size most M.
4

---

Under review as a conference paper at ICLR 2021
Select ensemble
Sample parent
Update population
J
Mutate
Figure 2: Illustration of one iteration of NES-RE. Network architectures are represented colored bars of different lengths illustrating different layers and widths. Starting with the current population, ensemble selection is applied to select parent candidates, among which one is sampled the parent. mutated copy of the parent is added to the population, and the oldest member is removed.
Note that while gradient-based NAS methods have recently become popular, they are not naively applicable in our setting as the base learner selection component ForwardSelect is typically non-differentiable.
4.1 NES WITH RANDOM SEARCH
In NAS, random search (RS) is a competitive baseline on carefully designed architecture search spaces (Li & Talwalkar, 2019 Yang et al.) 2020; Yu al., 2020). Motivated by its success and simplicity, we first introduce NES with random search (NES-RS RS). NES-RS builds the pool P by independently sampling architectures uniformly from the search space A (and training them). Since the architectures of networks in P vary, applying ensemble selection is simple way to exploit diversity, yielding a performant ensemble. Algorithm [ describes NES-RS in pseudocode.
Algorithm 1: NES with Random Search
Data: Search space A: ensemble size M; comp. budget K; Duain: Dval- Sample K architectures o1,...., . independently and uniformly from A.
Train each architecture a; using Durain yielding a pool of networks P ofe........ ax Select base learners [Jot.a]:.... .........>>................. ....,..,,,,a,, S0z
forwardSele leseleettte. (P, Deat, M) by forward step-wise selection without replacement.
return ensemble Br.semble(fe) .f.......... fei.......tt.. Soinars)
4.2 NES WITH REGULARIZED EVOLUTION
A more guided approach for building the pool P is using regularized evolution (RE) (Real et al. 2019). While RS has the benefit of simplicity, by sampling architectures uniformly, the resulting pool might contain many weak architectures, leaving few strong architectures for ForwardSelect to choose between. Therefore, NES-RS might require large pool in order to explore interesting parts of the search space. RE is an evolutionary algorithm used for NAS which explores the search space by evolving a population of architectures. In summary, RE starts with randomly initialized fixed-size population of architectures. At each iteration, subset of size m of the population is sampled. from which the best network by validation loss is selected as the parent. A mutated copy of the parent architecture, called the child, is trained and added to the population, and the oldest member of the population is removed, preserving the population size. This iterated until the computational budget is reached, returning the history, i.e. all the networks evaluated during the search, from which the best model chosen by validation loss.
Based on RE for NAS, we propose NES-RE to build the pool of potential base learners. NES-RE starts by randomly initializing a population p of size P. At each iteration, we apply Forwardse ect to the population to select ensemble of size m, and the ensemble to be the parent. A mutated copy the parent is added to p and the oldest network is removed, as in regularized evolution. This process is repeated until the computational budget is reached, and the history is returned as the pool P. See Algorithm for pseudocode and Figure for an illustration.
uniformly sample one base learner from
Also, note the distinction between the population and the pool in NES-RE: the population is evolved, whereas the pool is the set of all networks evaluated during evolution (i.e., the history) and is used
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2: NES with Regularized Evolution
Data: Search space A; ensemble size M: comp. budget K; Dunin, Deati population size P:
number of parent candidates m.
1
Sample P architectures o1,,..,, ar independently and uniformly from A.
Train each architecture a, using Prain and initialize p P (fe........ fop.ap)
3 while [P] < K do
Select m parent candidates ( 1 Jom. ForwardSelect D m).
s Sample uniformly a parent architecture a from ( am]
a stays in p.
Apply mutation to a, yielding child architecture 1.
7 Train 3 using Prrin and add the trained network fa.a to and P.
Remove the oldest member in
// as done in RE Real at al. 2019 } ForwardSelect(P (P, Deal M) by forward
9 Select base learners {foj.at...... - step-wise selection without replacement. return ensemble Ensemble (for.at ..... (0)
post-hoc for selecting the ensemble, similar to Real et al. (2019). Moreover, ForwardSelect is used both for selecting m parent candidates (line 4 in NES-RE) and choosing the final ensemble of size M (line 9 in NES-RE). In general, m f M.
4.3 ENSEMBLE ADAPTATION TO DATASET SHIFT
Using deep ensembles is a common way of building a model robust to distributional shift relative to training data. In general, one may not know the type of distributional shift that occurs at test time. However, by using an ensemble, diversity in base learner predictions prevents the model from relying on one base learner's predictions which may not only incorrect but also overconfident.
We assume that one does not have access to data points with test-time shift at training time, but one does have access to some validation data Dshift with a validation shift, which encapsulates one's belief about test-time shift. Crucially, test and validation shifts are disjoint. A simple way to adapt NES-RS and NES-RE to return ensembles robust to shift is by using Dzhilt instead of D whenever applying Forwar dSelecee to select the final ensemble. In algorithms aad [ this is in lines 3 and 9 respectively. Note that in line of Algorithm 2. we can also replace D with Dshint when expecting test-time shift, however to avoid running NES-RE once for each of Pral, Dehin we simply sample one of vaat: Dshift uniformly at each iteration, in order to explore architectures that work well both in-distribution and during shift. See Appendices C.1.3 and B.4 for further discussion.
5 EXPERIMENTS
We compare NES to deep ensembles on different choices of architecture search space (DARTS and NAS- NAS-Bench-200 (Dong & Yang 2020) search spaces) and dataset (FMNIST, CIFAR- 10, CIFAR-100. ImageNet- 6- 120 and Tiny Ieag. For CIFAR 10/100 and Tiny ImageNet, we also consider dataset shifts proposed by Hendryykk & Dietterich 2019). The metrics used are: NLL., classification eиror and expected calibration error (ECE) (Guo et al. 2017 Nacini et al.) 2015). Hyperparame-
3.43
LX
1.5
3.33
1.5
43
3
LG5
4.2
2.50
1.0
1.3
10
10
Encor Cao
Paloedasci 110
4 420
(a) No data shift
(b) Dataset shift: severity 5 (out of 5)
Figure 3: NLL ensemble sizes on CIFAR-10, CIFAR- 100 and Tiny ImageNet with and without respective dataset shifts (Hendrycks & Dietterich 2019) over DARTS search space.

---

Under review as a conference paper at ICLR 2021
3.43
1.32
2.28
1.34
2.53
2.70
6.31
3:35
3.09
6.30
1.0
3:00
L-30
2.66
reb erauuted
15th enw.uate
PeD evaladed
+d5 enalered
(a) No data shift
(b) Dataset shift: severity 5 (out of 5)
Figure 4: NLL vs. budget K on CIFAR-10/100 and Tiny ImageNet with and without respective dataset shifts over the DARTS search space. Ensemble size is fixed at M = 10.
ter choices, experimental and implementation details are available in Appendix B Unless stated otherwise, all evaluations are on the test dataset. Additional experimental results Appendix C
Baselines. We compare the ensembles found by NES to the baseline of deep ensembles built using a fixed, optimized architecture. On the DARTS search space, the fixed architecture is either: (1) opti- mized by random search, called DeepEns (RS), (2) the architecture found using the DARTS algorithm, called DeepEns (DARTS) or (3) the architecture found using RE, called DeepEns (AmoebaNet). On the HAS-Beech-2201 search space, instead of DnepEns DARTS/AmoebaNeet we compare to DeepEns (GDAS), found using GDAS (Dong & Yang 2019 and DeepEns (Optimal), which uses the optimal architecture in the NAS-Bench-201 search space by validation loss. All base learners use the same training routine and have approximately the same model size for given search space and dataset. See Appendix B for details and further discussion.
Computational cost analysis. NES algo- rithms typically have lower computational cost than deep ensembles of optimized architectures. There two sources of computational cost for the deep ensemble baselines: 1. searching for the fixed base learner architecture (which in- volves training and evaluating some number of architectures depending on the NAS algorithm used) and 2. training M initializations of it. On the other hand, NES does not require these two steps; the only source of cost for NES-RS and NES-RE is training the networks to build a pool, because ensemble selection from trained pool of networks is much cheaper. Running a NES al- gorithm with pool size K requires training only K networks. However, DeepEns (RS), for in- stance, has cost k - -M where & is the number of networks trained during random search to find the optimized architecture. In our experiments, we set k K, so NES-RE and NES-RS are cheaper than DeepEns (RS). Figure 4 compares NES algorithms and DeepEns (RS) as a function of K. Appendix C.3 describes a study in which we consider another (more expensive) baseline: optimize the fixed architecture, train K initializations of it and use Horwardse ect to select an ensemble of size M (where M < K). Appendix C.3 also includes further discussion of cost.
Table 1: Classification error of ensembles for dif- ferent shift severities. Best values and all values within 95% confidence interval are bold faced.
(a) M 10; DARTS search space.
Shift Severity
Clasif,, ernor (%), A - DARTS seurch space
Daitaset
DeepEns (Amos.)
Deeplis (DARTS)
DeepIns (RS)
NES-RS
NES-RE
0
9.7
10.0
10.8.as
9.4
9.4.12
C10
25.8
26.3
20.1
22 9.0.
42.7
42.9
38.0
37 420
31.6
30.9
$3.2-11
30. 711.
30 420.
66.2
55.1
68.5
65.5
643..3
62.4112
61.4111
ImageNNet
Tlay
38.5
71.7
55.4
54.6
71.6
53.8
70.3
03/0era
60.9
70.2
07.0
7an
(b) = 3: NAS-Bench-201 search space.
Dutaset
Shift Severity
Clessif, erree (9). = NAS Bench- 2011 search space
(GDAS)
(Optimal)
(RS)
D
5.4
7.2
T.aus
7.7
7,6eaa
C10
96-7
22.1
38.3
22 22
32.5
5
47.8
46.3
87.1
32.5
38.0m
26.3a44
28.8
23.5.aa
60.7
6000
Immu:Nes-16-12
0
69.9
40.9
00.50s
48.1.1m
47 47.9
NLL on in-distribution and shifted data. Figures 3a and 4a show the NLL achieved by NES-RS, NES-RE and the baselines as functions of the ensemble size M and budget K respectively for in-distribution data. We find that NES algorithms consistently outperform deep ensembles across
We did not consider DARTS algorithm on B---BBnch-220 since it returns degenerate architectures with poor performance this space (Dong & Yang 2020). GDAS, on the other hand, yields state-of-the-art performance on this space (Dong & Yang 2020).
7

---

Under review as a conference paper at ICLR 2021
ensemble sizes, with NES-RE usually outperforming NES-RS. Next, evaluate the robustness of the ensembles to dataset shift in Figures 3b] and 4b All base learners are trained on Duain without data augmentation with shifted examples. However, we use shifted validation dataset, D and shifted test dataset, Detan Dehin is built by applying random validation shift to each datapoint in Dval- Dibil is built similarly but using instead disjoint set of lest shifts applied to Diesti see Appendix [ and Hendrycks & Dietterich (2019) for details. The severity of the shift varies between 1-5. The fixed architecture used in the baseline DeepEns (RS) is selected based on its loss over D Dehif but the DARTS and AmoebaNet architectures remain unchanged. As shown in Figures 33 and [4b] ensembles picked by NES-RS and NES-RE are more robust to dataset shift than all three baselines. Unsurprisingly, DeepEns they are not optimized to deal with dataset shift, highlighting that highly optimized architectures can fail heavily under dataset shift.
perform poorly compared to the other methods, as
Classification error and uncertainty calibration. We also assess the ensem- bles using classification error and ex- pected calibration error (ECE). ECE measures the mismatch between the model's 's confidence and the correspond- ing achieved accuracy at different levels of confidence. As shown in Figure [ ensembles found with NES tend to ex- hibit superior uncertainty calibration and either competitive with or outperform deep ensembles for most shift severities. Notably, on CIFAR-10, 10, ECE reduces by up to 40% compared to deep ensembles. Note that good uncertainty calibration is especially important when models are used during dataset shift. In terms of classification error, we find that ensembles built by NES consistently outperform deep ensembles, with reductions of up to 7 percentage points in error, shown in T As with NLL., NES-RE tends to outperforms NES-RS.
CFAR-10
CIFAR-100
Thny' ImageNet
0.54
0.12
0.12
8
0.10
0.06
Shit severty
S1 severty
SWiT severyy
Figure 5: ECE vs. dataset shift severity CIFAR- 10, CIFAR-100 and Tiny ImageNet over the DARTS search space. No dataset shift is indicated severity 0. Ensem- ble size is fixed at M = 10.
Diversity and average base learner strength. To understand why ensembles found by NES algorithms outperform deep ensembles with fixed, optimized architectures, we view the ensembles through the lenses of the average base learner loss and oracle ensemble loss as defined in Section 3 and shown in Figure 6 Recall that small oracle ensemble loss indicates higher diversity. We see that NES finds ensembles with smaller oracle ensemble losses indicating greater diversity among base learners. Unsurprisingly, the average base learner is occasionally weaker for NES as compared to DeepEns (RS). Despite this, the ensemble performs better (Figure 3), highlighting once again the importance of diversity.
Results on the NAS-Bench-201 search space. We also compare NES to deep ensembles for the NAS-Bench-201 search space, which has two benefits: this shows our findings are not specific to the DARTS search space, and 201 is a search space for which all ar- chitectures' trained weights are available, which allows us to compare NES to the deep ensemble of the optimal architec- ture by validation loss. Results shown in Figure compare the losses of the en- semble, average base learner and oracle ensemble. Interestingly, despite DeepEns (Optimal) having a significantly lower average base learner loss than other methods, the lack of diversity (as indicated by higher oracle ensemble loss) yields an ensemble which is outperformed by both NES algorithms.
Imag=1eet-161120
magekket-166120
1.50
1.55
2200
1:0
2.122
250 300 150
3000
250
5000
750
1000
250
500
150
1000
Figure 7: Ensemble, average base learner and oracle en- semble NLL for ImageNet- 120 on the MAS-BBnnh-- search space. Ensemble size M = 3.
Further comparisons and studies. additional baselines. In Appendix
In Appendices C.3 and C.4 we compare NES to a number of we consider deep ensembles with ensemble selection over
8

---

Under review as a conference paper at ICLR 2021
1..55
1-01
0.50
2.00
0.70
AND
3.70
1.70
Dieamblee sex 611
Croemble 3am (M)
Exienbi cN 181
Craemibe 00
Eriemble sox MM
Drsemble sibe PO
Figure Average base learner loss and oracle ensemble loss (see Section 3 for definitions) on CIFAR-10/100 and Tiny ImageNet. Recall that small oracle ensemble loss generally corresponds to higher diversity. These findings are qualitatively consistent across datasets and also over shifted test data. See Appendix C.1
random initializations of a fixed architecture to ascertain whether the improvement in NES is only due to ensemble selection. Our results show that NES continues outperform this baseline affirming the importance of varying the architecture. In Appendix C.4 we consider baselines of ensembles with other hyperparameters being varied. In particular,
consider ensembles with fixed, optimized architecture but varying learning rates and L2 regularization strengths (similar to concurrent work by Wenzel al. (2020)) and ensembles with architectures varying only in terms of width and depth. The results again show that NES tends to improve upon these baselines.
6 CONCLUSION
We showed that ensembles with varying architectures are more diverse than ensembles with fixed architectures and argued that deep ensembles with fixed, optimized architectures neglect diversity. To this end, we proposed Neural Ensemble Search, which exploits diversity between base learners of varying architectures to find strong ensembles. We demonstrated empirically that NES-RE and NES-RS outperform deep ensembles in terms of both predictive performance and uncertainty calibration, for in-distribution data and also during dataset shift. We found that even NES-RS, simple random search based algorithm, found ensembles capable of outperforming deep ensembles built with state-of-the-and architectures.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. In International Conference on Learning Representations, 2020. URL
wttpriiwweeee..eee net net. Forum Bee.d-BBIIigHHg
Yijun Bian and Huanhuan Chen. When does Diversity Help Generalization in Classification Ensem- bles? ArXiv, 0hs//1003.02236 2019.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. End to End Learning for Self-Driving Cars. CoRR, abs/1604.07316, 2016.
Leo Breiman. Random forests. In Machine Learning, pp. 5-32, 2001.
Rich Caruana, Alexandru Niculescu-Mizil, Geoff Crew, and Alex Ksikes. Ensemble Selection from Libraries of Models. In Proceedings of the Twenty-First International Conference Machine Learning, ICML '04, pp. 18, New York, NY, USA, 2004. Association for Computing Machinery. doi: 10.1 10.1145/1015330.101555 1014443. Utthttts:://// /RL/htps:://ooo.oo///0.....
ISBN 1581 138385,
1015330 1015432
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint 177.v01707.08819 2017.
Corinna Cortes, Xavier Gonzalvo, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. AdaNet: Adap- tive Structural Learning of Artificial Neural Networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 Proceedings of Machine Learning Research, pp. 574-883 International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL http::/proceedi.ng .mw.eeddiinsmm.......mmmmm.m.m.m www. htwp://www............e...
hore/s/rrssssoeeooo html
Thomas G. Dietterich. Ensemble Methods in Machine Learning. In Multiple Classifier Systems, pp. 1-15, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. ISBN 978-3-540-4501446
Xuanyi Dong and Yi Yang. Searching for Robust Neural Architecture in Four GPU Hours. In Computer Vision and Pattern Recognition (CVPR), pp. 1761-1770, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-200 201: Extending the scope of reproducible neural architecture search. International Conference on Learning Representations (ICLR), 2020. URL https
o/ppenrvveew. net
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural Architecture Search: A Survey.
Journal of Machine Learning Research, 20(55):1-21, 2019.
Andre Esteva, Brett Kuprel, Roberto A. Novoa, Justin Ko, Susan M. Swetter, Helen M. Blau, and Sebastian Thrun. Dermatologist-level classification of skin cancer with deep neural networks. Nature, 542:115-, 2017.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and Efficient Hyperparameter Optimization Scale. In Proceedings the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1437-1446, Stockholmsmässsn, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:://rocceed.gg... mlr prrppp press/ 1500falknerr8a.fig
Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Springenberg, Manuel Blum, and Frank Hutter. Efficient and robust automated machine learning. In Advances Neural Information Processing Systems 28, pp. 2962-2970. Curran Associates, Inc., 2015.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep Ensembles: A Loss Landscape
Perspective. ArXiv, abs/1912.02257, 2019.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. volume 48 of Proceedings of Machine Learning Research, pp. 1050- 1059. New York, New York, USA, 20-22 Jun 2016. PMLR. URL hattp://proceeeinngs ptr.pres//v4...
html
10

---

Under review as a conference paper at ICLR 2021
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On Calibration of Modern Neural Networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1321-1332 International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL http:p:t//p/ooooettotoee httt:::/pprocee.ngss.ll... mlr press/
v70 770/quo17a... html
Fredrik K Gustafisonn, Martin Danelljan, and Thomas B Schön. Evaluating Scalable Bayesian Deep Learning Methods for Robust Computer Vision. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2020.
Lars K. Hansen and Peter Salamon. Neural network ensembles. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(10):993-1011, 1990.
Bobby He, Balaji Lakshminarayanan, and Yee Whye Teh. Bayesian deep ensembles via the neural tangent kernel. arXiv preprint 2XXi:2007700864 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking Neural Network Robustness to Common Corruptions and Perturbations. In International Conference on Learning Representations, 2019.
G. Hinton, L. Deng, D. Yu, G. E. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 29(6):82-97, 2012.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John Hopcroft, and Kilian Weinberger. Snapshot Ensembles: Train 1, get m for free. In International Conference on Learning Representations, 2017.
Hutter, L. Kotthoff, and Vanschoren (eds.). Automated Machine Learning: Methods, Systems, Challenges. Springer, 2018. In press, available at http://automl.orr/hogg
Siddhartha Jain, Ge Liu, Jonas Mueller, and David Gifford. Maximizing overall diversity for improved uncertainty estimates in deep ensembles. Proceedings of the AAAI Conference on Artificial Intelligence, 44(04)):464442777 htttps://ojs. aaai. org/ balzg/indde wiwiiiiixxx////// http///A///aatiee/////////////
Apr. 2020. doi: 10.1609/aaii wttp/////aa..340...888.8 v34104.589. URL
Zhengshen Jiang, Hongzhi Liu, Bin Fu, and Zhonghai Wu. Generalized Ambiguity Decompositions for Classification with Applications in Active Learning and Unsupervised Ensemble Pruning. In AAAI, pp. 2073-2079. AAAI Press, 2017.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). 2009. URL URL pottp://wwen cs www.sttoontooooooooo www.nto................ http:/tt...euu/kkii//.......rrr. htmmlllia.....m..lll.m
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet Classification with Deep Convo- lutional Neural Networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097-1105. Curran Associates, Inc., 2012.
Anders Krogh and Jesper Vedelsby. Neural Network Ensembles, Cross Validation, and Active Learning. G. Tesauro, D. Touretzky, and T. Leen (eds.), Advances Neural Information Processing Systems 7, pp. 231-238. MIT Press, 1995.
Ludmila Kuncheva and Chris Whitaker. Measures of Diversity in Classifier Ensembles and Their Relationship with the Ensemble Accuracy. Machine Learning. 51:181-207, 05 2003. doi: 10.1023/A:102285900333
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles. In Advances in Neural Information Processing Systems 30, pp. 6402-6413. Curran Associates, Inc., 2017.
11

---

Under review as a conference paper at ICLR 2021
Y. Le and X. Yang. Tiny imagenet visual recognition challenge. 2015.
Stefan Lee, Senthil Purushwalkam, Michael Cogswell, David Crandall, and Dhruv Batra. Why M Heads are Better than One: Training a Diverse Ensemble of Deep Networks. arXiv e-prints, art. 2015.
Jalien-Charles I Lévesque, Christian Gagné, and Robert Sabourin. Bayesian hyperparameter optimiza- tion for ensemble learning. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI'16, pp. 437-446 Arlington, Virginia, USA, 2016. AUAI Press. ISBN 978099664315..
Liam Li and Ameet Talwalkar. Random Search and Reproducibility for Neural Architecture Search. In UAI, pp. 129. AUAI Press, 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable Architecture Search, In International Conference on Learning Representations, 2019.
Y. Liu and X. Yao. Ensemble learning via negative correlation. Neural networks: the official journal of the International Neural Network Society, 12 10:1399-1404, 1999.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. In International Conference Learning Reprexentations, 2017.
Vladimir Macko, Charles Weill, Hanna Mazzawi, and Javier Gonzalvo. Improving Neural Architec- ture Search Image Classifiers via Ensemble Learning. ArXiv, Se////033006255 2019.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed Representations of Words and Phrases and their Compositionality. In Advances in Neural Information Processing Systems 26, pp. 3111-3119, Curran Associates, Inc., 2013.
Mahdi Pakdaman Naeini, Gregory F. Cooper, and Milos Hauskrecht. Obtaining Well Calibrated Probabilities using Bayesian Binning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI 15, pp. 2901-2907. AAAI Press, 2015. ISBN 026251 1290.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? Evaluating predictive uncertainty under dataset shift. In Advances in Neural Information Processing Systems Curran Associates, Inc., 2019.
32, pp. 13991-14002
Tim Pearce, Felix Leibfried, and Alexandra Brintrup. Uncertainty in neural networks: Approximately bayesian ensembling. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 234-244, Online, 26-28 Aug 2020. PMLR. URL http: //proceedings.co mlr prwss v108 http//////eeaaeeeeeee wwtpp/eaaaaaaaaaeaaee html
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized Evolution for Image Classifier Architecture Search. AAAI, pp. 4780-4789, AAAI Press, 2019. ISBN 978-1-57735- 809-1.
Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. In International Conference on Learning Representations, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going Deeper with Convolutions. In Computer Vision and Pattern Recognition (CVPR), 2015.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE, Journal of Machine Learning Research, 9(2579-260)) 2008
Andrew M. Webb, Charles Reynolds, Dan-Andrei Iliescu, Henry W. J. Reeve, Mikel Luján, and Gavin Brown. Joint Training of Neural Network Ensembles. CoRR, abs/1902.04422,, 2019.
Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML'11 11, pp. 681-688 Madison, WI, USA, 2011. Omnipress. ISBN 978199789500 1500066195
12

---

Under review as a conference paper at ICLR 2021
Florian Wenzel, Jasper Snoek, Dustin Tran, and Rodolphe Jenatton. Hyperparameter ensembles for robustness and uncertainty quantification, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: A Novel Image Dataset for Bench- marking Machine Learning Algorithms. arXiv e-prints, 2017.
Antoine Yang, Pedro M. Esperança, and Fabio M. Carlucci. NAS evaluation is frustratingly hard. In International Conference on Learning Representations, 2020.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluat- ing the Search Phase Neural Architecture Search. International Conference on Learning Representations, 2020.
Tianyi Zhou, Shengjie Wang, and Jeff A Bilmes. Diverse Ensemble Evolution: Curriculum Data- Model Marriage. In Advances in Neural Information Processing Systems 31, pp. 5905-5916. Curran Associates, Inc., 2018.
Zhi-Hua Zhou. Ensemble Methods: Foundations and Algorithms. Chapman & Hall, 1st edition, 2012. ISBN 1439830037.
Zhi- Zhi-Hua Zhou, Jianxin Wu, and Wei Tang. Ensembling neural networks: Many could be better than all. Artificial Intelligence, 137(1):239 263, 2002. ISSN 0004-3702. doi: https://doi.or//100 1016/ (0004-3702(02)00115
Barret Zoph and Quoc V Le. Neural Architecture Search with Reinforcement Learning. In Interna- tional Conference on Learning Representations, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning Transferable Architectures for Scalable Image Recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8697-8710, 2018
13

---

Under review as a conference paper at ICLR 2021
A
PROOF OF PROPOSITION 3.1
Taking the loss function to be NLL, we have {(f()),)) y) = =- log [f(x)]y. where [f(x]ly is the
probability assigned by the network of belonging the true class i.e. indexing the predicted probabilities f(z) with the true target y. Note that t + - log is a convex and decreasing function.
We first prove (Fou(()) v) ((F(x)) Recall, by definition of Fog, we have (ou(x) fe, (x) where & E argmin; {.fo, (æ), y), therefore [Fon(z)]ı = [o, (z)]y 2 (x),y for all i = 1...., C. That is, S0, assigns the highest probability the correct class y for input æ. Since loog is decreasing function, we have
((F(x). v) = log
M (x)ly)))))
log (Ifor (x)1y) ([all)))((FFee((() ((Foe()),)))
We apply Jensen's inequality in its finite form for the second incquality. Jensen's incquality states that for a real-valued, convex function ip with its domain being a subset of R and numbers f1 i,,...; in its domain, ( Ei= t.) I :. Ei (t,)). Noting that log is convex function, ((F(xz).))
, In
1 Σ i==1 L(fe, (x), y) follows directly. M
B EXPERIMENTAL AND IMPLEMENTATION DETAILS
We describe details of the experiments shown Section and Appendix C Note that unless stated otherwise, all sampling over discrete set is done uniformly in the discussion below.
B. ARCHITECTURE SEARCH SPACES
DARTS search space. The first architecture search space we consider in our experiments is the one from DARTS (Liu et al. 2019). We search for two types of cells: normal cells, which preserve the spatial dimensions, and reduction cells, which reduce the spatial dimensions. These cells are stacked using pre-determined aachooarchitecctre where they usually repeated and connected using additional skip connections. Each cell is a directed acyclic graph, where nodes represent feature maps in the computational graph and edges between them correspond to operation choices (e.g. convolution operation). The cell parses inputs from the previous and previous-previous previous cells in its 2 input nodes. Afterwards it contains 5 nodes: 4 intermediate nodes that aggregate the information coming from 2 previous nodes in the cell and finally an output node that concatenates the output of all intermediate nodes across the channel dimension. AmoebaNet contains one more intermediate node, making that deeper architecture. The set of possible operations (eight in total in DARTS) that we use for each edge in the cells is the same as DARTS, but we leave out the "zero" operation since that is not necessary for non-differentiable approaches such as random search and evolution. Randomly of architectures is done by sampling the structure of the cell and the operations at each edge. The total number of architectures contained in this space is 18 We refer the reader to Liu et al. 2019) for more details.
NAS-Bench-201 search space. MAS-Bench-201 (Dong & Yang 2020 is tabular NAS bench- mark, i.c. all architectures in the cell search space are trained and evaluated beforehand so one can query their performance (and weights) from a table quickly. Since this space is exhaustively evaluated, its size is also limited to only normal cells containing 4 nodes in total (1 input, 2 intermediate and 1 output node) and operation choices on every edge connecting two nodes. This means that there are only 15,625 possible architecture configurations in this space. The networks are constructed by stacking 5 cells with in-between fixed residual blocks for reducing the spacial resolution. Each of them is trained for 200 epochs 3 times with 3 different seeds on 3 image classification datasets. For more details, please refer to Dong & Yang (2020).
B.2 DATASETS
Fashion-MNIST Xiao et al. 2017). Fashion-MNIST consists of training set of 60k 28x28 grayscale images and test set of 10k images. The number total labels 10 classes. We split the 60k training set images 50k used to train the networks and 10k used only for validation.
14

---

Under review as a conference paper at ICLR 2021
CIFAR-10/100 (Krizhevsky et al., 2009).
CIFAR- 10 and CIFAR-100 both consist of 60k 32x32 colour images with 10 and 100 classes, respectively. We use 10k of the 60k training images as the validation set. We use the 10k original test set for final evaluation.
Tiny ImageNet (Le & Yang 2015). Tiny Imagenet has 200 classes and each class has 500 training, 50 validation and 50 test colour images with 64x 64 resolution. Since the original test labels are not available, split the 10k validation examples into 5k for testing and 5k for validation.
This variant of the ImageNet- 16-120 (Chaaaazzzz et al. 2017) contains 151.7k train, 3k validation and 3k test ImageNet images downsampled to 16x 16 and 120 classes.
ImageNet-166 120 (Dong& & Yang, 2020)
Note that the test data points are only used for final evaluation. The data points for validation are used by the NES algorithms during ensemble selection and by DeepEns (RS) for picking the best architecture from the pool to use in the deep ensemble. Note that when considering dataset shift for CIFAR-10, CIFAR-100 and Tiny ImageNet, lowing the terminology used by (Hendrycks & Dietterich 2019)) to the validation and test sets. We never apply any corruption to the training data. More specifically, out of the 19 different corruptions provided by Hendrycks & Dietterich (2019), we randomly apply one from {Speckle Noise, Gaussian Blur, Spatter, Saturate] to each data point and one from (Gaussian Noise, Shot Noise, Impulse Noise, Defocus Blur, Glass Blur, Motion Blur, Zoom Blur, Snow, Frost,Foo Brightness, Cont Elastic Transform, Pixelate, JPEG compression] to each data point in the test set. This choice of validation and test corruptions follows the recommendation (Hendrycks & Diet- terich 2019). Also, mentioned in Section each of these corruptions has 5 severity levels, which yields corresponding severity levels for Damm and Dshift val
also apply two disjoint sets of "corruptions" (fol-
the validation set
lest
B.3 TRAINING ROUTINE
The macro-architecture we use has 16 initial channels and 8 cells (6 normal and 2 reduction), and was trained using a batch size of 100 for 100 epochs for CIFAR- 10 and CIFAR-100 and 15 epochs for Fashion-MNEE MNIST. For Tiny ImageNet, we used a batch size of 128 for 100 epochs. Unlike DARTS, we do not use any data augmentation procedure during training, nor any additional regularization such as ScheduledDropPath (Zoph et al.) (018) or auxiliary heads, except for the case of Tiny ImageNet, for which we used ScheduledDropPatt and standard data augmentation as default in DARTS. All other hyperparameter settings are exactly as in DARTS (Liu et al. 2019).
All results shown are averaged over multiple runs with error bars indicating a 95% confidence interval. We used a budget K 400 in all experiments, except Tiny ImageNet the DARTS search space, which used K 200 and ImageNet-16-1 120 on the M'S--Bnnc-22 201 search space, which used K 1000.
B.4 IMPLEMENTATION DETAILS OF NES-RE
Parallization. Running NES-RE single GPU requires evaluating hundreds of networks se- quentially, which is tedious. To circumvent this, we distribute the "while |P| < K" loop in Algorithm 2 over multiple GPUs, called worker nodes. We use the parallelism scheme provided by the hpbandster (Falkner et al. 2018) codebase In brief, the master node keeps track of the population and history (lines I, 4-6, Algorithm 2). and distributes the training of the networks to the individual worker nodes (lines 2, 7 in Algorithm
2). In our experiments, we always use 20 worker nodes and evolve population p of size P 50 when working over the DARTS search space. Over MAS-Bench-201, we used one worker since it is a tabular NAS benchmark and hence is quick to evaluate on. During iterations of evolution, we use an ensemble size of m 10 to select parent candidates.
Mutations. We adapt the mutations used in RE to the DARTS search space. As in RE, we first pick a normal or reduction cell at random to mutate and then sample one of the following mutations:
httpp:://github.com http:/uttttmmmllinndsddtttr
15

---

Under review as a conference paper at ICLR 2021
identity: mutation is applied to the cell.
op mutation: sample one edge in the cell and replace its operation with another operation sampled from the list operations.
hidden state mutation sample intermediate node in the cell, then sample one of its two incoming edges. Replace the input node of that edge with another sampled node, without altering the edge's operation.
See Real et al. (019) for details and illustrations these mutations. Note that for HAS-Bench-201, following Dong & Yang 2020) we only use op mutation.
Adaptation of NES-RE to dataset shifts, As described in Section 4.3 at each iteration of evolu- tion, the validation set used in line 4 of Algorithm 2 is sampled uniformly between D and D when dealing with dataset shift. In this case, use shift severity level 5 for Dehinn Once the evolution complete and the pool P has been formed, then for each severity level & E {0. 1.....5,,, 5), we apply ForwardSelect with Dehift of severity to select ensemble from P (line 9 in Algorithm 2). which is then evaluated on Dahin of severity s. (Here 0 corresponds no shift.) This only applies to CIFAR-10, 10, CIFAR-100 100 and Tiny ImageNet, as we do not consider dataset shift for Rashion-MNIST and ImageNet-16-1200
16

---

Under review as a conference paper at ICLR 2021
C ADDITIONAL EXPERIMENTS
In this section we provide additional results for the experiments conducted in Section 5 Note that, as with all results shown in Section all evaluations made on data unless stated otherwise.
C.I ADDITIONAL RESULTS ON THE DARTS SEARCH SPACE
C.1.1 RESULTS ON FASHION-MNISS
M
M - 10
30
0.255
0.22
0.215
0.210
NIL (00 (003389
0.210
0.05
0.205
Sarpfin (fonsesabit)
0.205
0200
0.20
0.200
0.195
100
200
400
Number networks
Number
Figure 7: Results on FaSSIon-MNIST with varying ensembles sizes M. Lines show the mean NLL achieved by the ensembles with 95% confidence intervals.
M
0.240
Average base lotrner
0.235
0.35
0.25
MES-6
NC5
NL1 (he SPRR!
Docsbri IhS1
0.230
0.230
0.230
0.24
SeepEne (DARTO
Doceens (Amzesshet)
0.225
0.25
0.220
0.200
0.220
0.22
100
200
300
400
100
200
300
400
100
200
300
400
100
200
300
400
Number of networkks evaluated
Number of networks evalunted
Number of netyoris evalisstd
Number of networrks evaiuated
Figure 8: Average base learner loss for NES-RS, NES-RE and DeepEns (RS) on Fasshon-MMISS Lines show the mean NLL and 95% confidence intervals.
M
M
M = 10
M 30
Oradee entemble
NL (ho shitt
0.155
0.130
0.135
0.110
0.085
KES RE
NBS RS
Deestro
0.105
0.060
0.100
0.120
0.075
0.055
0.135
0.115
100
1000
200
Number networks evalusted
evalusted
evaluated
evalusted
Figure 9; Oracle ensemble loss for NES-RS, NES-RE and DeepEns (RS) Fashion-MNIST. Lines show the mean NLL and 95% confidence intervals.
As shown in Figure 7 ensembles outperform deep ensembles with NES-RE outperforming NES-RS. To understand why
see similar trend on Fashion-MNIST with other datasets: NES
NES algorithms outperform deep ensembles on FaShion-MNIST (Xiao al. 2017). we compare the average base learner loss (Figure (8) and oracle ensemble loss (Figure 9 of NES-RS, NES-RE and
DeepEns (RS). Notice that, apart from the case when ensemble size M 30, NES-RS and NES-RE find ensembles with both stronger and more diverse base learners (smaller losses in Figures 8 and 9 respectively). While it is expected that the oracle ensemble loss smaller for NES- and NES-RE compared to DeepEns (RS), it initially appears surprising that DeepEns (RS) has larger average base learner loss considering that the architecture for the deep ensemble is chosen to minimize the base learner loss. We found that this is due to the loss having sensitive dependence not only on the architecture but also the initialization architecture by validation loss to build the deep ensemble yields base learners with higher losses due to the use of different random initializations. Fortunately, NES algorithms are not affected by this, since they simply select the ensemble's base learners from the pool without having re-train anything
the base learner networks. Therefore, re- te-training the best
17

---

Under review as a conference paper at ICLR 2021
which allows them to exploit good architectures well as initializations. Note that, for CIFAR-10- 10-C experiments, this was not the case; base learner losses did not have as sensitive a dependence on the initialization they did on the architecture.
In Table 2 we compare the classification error and expected calibration error (ECE) of NES algorithms with the deep ensembles baseline for various ensemble sizes NES algorithms also achieve smaller errors, while ECE remains approximately the same for all methods.
Similar to the loss,
Table 2: Error and ECE of ensembles on Fashion-MNIST for different ensemble sizes M. Best values and all values within 95% confidence interval are bold faced.
Classification Error (out of
Expected Calibration Error (ECE)
NES-RS RSS-RR
NES-RE
Deeplias (RS)
DeepPins (DARTS)
DnepEns (AmoebaNet)
NES-RS
NES-RE
DeepFins (RS)
DeepEns (DARTS)
DeepEns (AmoehaNet)
0,074410
0.072.0001
0.0761o
0.077
0.077
0.007-6.00
0.007
0 1.00810.00
0.003
0,008
0.006
10
0.075
0.076 0.075
0.073
0.004
0.00
0.006
0.006
0.005
30
0.073
0.070
0.074
0.073
0.004:-mm
0. 0.004
a.004
0.008
0.004
C.1.2 ENTROPY ON OUT-OFF-DSTTRIBTIOO INPUTS
To assess how well models respond completely out-of-distribution (OOD) inputs (inputs which do not belong to one of the classes the model can predict), we investigate the entropy of the predicted probability distribution over the classes when the input OOD, Higher entropy of the predicted probabilities indicates more uncertainty in the model's output. For CIFAR-10 on the DARTS search space, we compare the entropy the predictions made by NES ensembles with deep ensembles on two types of OOD inputs: images from the SVHN dataset and Gaussian noise. In Figure [T0 we notice that NES ensembles indicate higher uncertainty when given inputs of Gaussian noise than deep ensembles but behave similarly to deep ensembles for inputs from SVHN.
1.0-
3.8
0.2
3.2
3.0
3.5
1.0
1.5
2.0
2.0
0.5
3.0
1.5
2.0
0.0
0.5
1.0
1.5
0.5
1.0
15
Entropy
Entrony
Entropy
Entrary
Figure 10: Entropy of predicted probabilities when trained on CIFAR-10 over the DARTS search space.
C.1.3 ADDITIONAL RESULTS ON CIFAR-10, CIFAR- 100 AND TINY IMAGENET
In this section, we provide additional experimental results on CIFAR-10, 10, CIFAR-100 and Tiny ImageNet the DARTS search space, complimenting the results in Section ass shown in Figures 12-18.
18

---

Under review as a conference paper at ICLR 2021
Faxt ass
t-SNN dimension
-2
b-SNE dimension 1
Figure 11: t-SNE visualization: predictions of base learners in two ensembles, one with fixed architecture and one with varying architectures.
CIRAR
CiRAK
2.00
2.28
2.33
1.28
2.20
144
2,23
1.4
10
10
(a) Data shift (severity 1)
(b) Data shift (severity 2)
Try
1.2
1.0
Encortie
2.45
2.82
232
Eraurbie 220
(c) Data shift (severity 3)
(d) Data shift (severity 4)
Figure 12: NLL ensemble sizes CIFAR-10, CIFAR-100 and Tiny ImageNet with varying dataset shifts (Hendrycks & Dietterich 2019 over DARTS search space.
19

---

Under review as a conference paper at ICLR 2021
3.8
2.32
2.33
2227
1.0
3.4
335
2.9
Ereambe 2o
fraunb
Guarddeaza
(a) No data shift
(b) Data shift (severity 1)
0.22
0.22
3/4
3.22
0.2
3:4
0.8
10
10
Ersomble see 191
Essorsleate 110
Draembe Met
e 190
Excrblesze II
Ersenbe see
(c) Data shift (severity 2)
(d) Data shift (severity 3)
CIFAR-10
21AB-300
Try Imagehet
CIPA8-10
CITAB-200
Try Imagthet
3.44
0.79
3,42
2:03
3:2
0.34
0.40
Ersomble sice 191
Exsorblezze 110
Craembx Mire
Craembe S0000
(c) Data shift (severity 4)
(i) Data shift (severity 5)
Figure 13: Classification error rate (between 0-1) vs. ensemble size on DARTS search space.
2.544
CIFAR11
CFAR-30
3.04
0.53
CFAR-10
GFAR 10
0.79
QFAR.13
testuree
0.00
0.32
6.50
3.30
20.90
Losete 2014
125
5.00
6.0
0.22
Anlevok 620
4Sar0i 628
Stawiick 20
Estmmbl 520
(a) No data shift
(b) Data shift (severity 1)
(c) Data shift (severity 2)
GPAB-10
CFAB-20
OPAR-13
CPAR-10
C34B-10
CPAR-13
3.75
3.53
3.53
2.20
2.00
1.00
Eniees
Droemide 210
Ersentle
Exveentee Het 11
Excemble Sie
Erienble vie
(d) Data shift (severity 3)
(c) Data shift (severity 4)
(f) Data shift (severity 5)
Figure 14: Average base learner and oracle ensemble NLL across ensemble sizes and shift severities on CIFAR-10 10 over DARTS search space.
20

---

Under review as a conference paper at ICLR 2021
CFAR-100
CIAAR-10
GPA8-110
1.93
CFAR-100
2.10
CIFA-1100
2033
CFFA-100
22.32
2220
L.4
0.75
659
62
(a) No data shift
(b) Data shift (severity
(c) Data shift (severity
CEAR-100
CIFAR-100
CIAA-100
CBAA0-102
07A6-130
CEAR-100
4.00
2.89
5.09
3.0
2.0
3.59
(d) Data shift (severity 3)
(c) Data shift (severity 4)
(f) Data shift (severity 5)
Figure 15: Average base learner and oracle ensemble NLL across ensemble sizes and shift severities on CIFAR- 100 over DARTS search space.
Try Imsgellet
Thy ImageNet
Thy Image Set
Thy Imagelet
Thny imspelet
2.0
Try Imageelet
3.30
LG2
paanne Roodh
2.22
2.22
Oh AANTA
3.03
2.2
2.72
10
22
26
10
23
10
(a) No data shift
(b) Data shift (severity
(c) Data shift (severity 2)
Imagelet
ImaggeNet
Imagelitt
Imagehet
imapetiet
Imagalist
2,53
2.75
3.2
6.00
2.2
2.00
2.00
10
12
2.50
(d) Data shift (severity 3)
(e) Data shift (severity 4)
(1 Data shift (severity 5)
Figure 16: Average base learner and oracle ensemble NLL across ensemble sizes and shift severities on Tiny ImageNet over DARTS search space.
21

---

Under review as a conference paper at ICLR 2021
CIFAK 10
CIFAR 1.00
Thy Imagefett
CIRAR
CPAR 100
Tny Imagefitt
1.35
032
1.50
2.00
1.40
2.70
1.5
1.55
15
2.
L10
1.70
1.51
300
56
236
326
300
230
208 oyelatt
(a) No data shift
(b) Data shift (severity 1)
CIFAR 10
CPARL1000
Thy Imagefict
CIPA--10
CFARL100
Try Imagetae
2.30
1.0
2.00
2,00
176
3.0
1.92
300
200
100
210
900
6.00
310
110
203
316
280
300
212
600
50
315
350
283
evalated
(c) Data shift (severity 2)
(d) Data shift (severity 3)
CIFA8-10 10
CFAR-100
Try Imagetter
CIPA-110
CFAR-100
Try Imagehett
2:30
3.23
110
4.30
244
3.5
1:25
330
3.20
2.42
300
200
330
100
230
300
630
50
330
350
207
306
200
300
430
320
235
330
600
52
330
350
252
(e) Data shift (severity 4)
(f) Data shift (severity 5)
Figure 17: Ensemble NLL vs. budget K. Ensemble size fixed at M = 10.
CIRAR-D
OFAR 1.00
Thy Imagetiet
CIRAR 30
CFAR-100
Thy Imagehir
032
0.34
0.33
0.32
2:30
0.22
2.2
8.37
0,28
020
300
330
350
238
338 mualuats
anl cite
(a) No data shift
(b) Data shift (severity 1)
CITAR-10
CIFAR, 100
Thy Imagetiet
CIAA8-10
CFARR100 1000
2.50
Thy Imagetiet
0.58
12.5
0.54
033
046
3.28
044
8.47
0.50
044
5.5
100
150
212
315
110
200
116
250
100
212
212
112
202
erdluttdd
exlated
(c) Data shift (severity 2)
(d) Data shift (severity 3)
CITAR-10
CFAA-100
Try Imagetiet
CIFA8-10
CFAR-100
Try Imagelic
0.32
0.28
3.32
3.58
3.4
0.44
3.39
337
0.58
300
100
210
$22
0.00
310
110
202
316
250
300
232
523
332
318
233
(e) Data shift (severity 4)
(I) Data shift (severity
Figure 18: Ensemble error vs. budget K. Ensemble size fixed at M- = 10.
22

---

Under review as a conference paper at ICLR 2021
CTM--300
(a) No data shift
(b) Data shift (severity 1)
(c) Data shift (severity 2)
12 12
colurnt
15 10
(d) Data shift (severity 3)
(e) Data shift (severity 4)
(1) Data shift (severity 5)
Figure 19: High fidelity NLL vs. budget K on CIFAR-10 10 and CIFAR- 100 with and without respective dataset shifts over the DARTS search space. Ensemble size is fixed at M 10.
4:30
(a) No data shift
(b) Data shift (severity 1)
(c) Data shift (severity 2)
OPANEE
DEAN-E
CPAN-3
(d) Data shift (severity 3)
(e) Data shift (severity 4)
(f) Data shift (severity 5)
Figure 20: High fidelity classification error vs. budget K on CIFAR- 10 and CIFAR- 100 with and without respective dataset shifts over the DARTS search space. Ensemble size is fixed at M 10.
Results on CIFAR for larger models. In additional to the results on CIFAR-10 and CIFAR-100 using the settings described in Appendix [B.3] we also train larger models (around 3M parameters) by scaling up the number of stacks cells and imitial channels in the network. We run NES and other baselines similarly as done before and plot results Figure 19 and 20 for NLL and classification test error with budget K = 90. As shown, NES algorithms tend to outperform or be competitive with the baselines. Note, more runs are needed including error bars for conclusive results in this case.
C.2 ABLATION STUDY: NES-RE OPTIMIZING ONLY ON CLEAN DATA
We also include variant of NES-RE, called NES-RE-O, in Figure 21 TINEERRE and NES-RE-O the same, except that NES-RE-O uses the validation set Dval without any shift during iterations of evolution, in line of Algorithm 2 unlike NES-RE, where we sample the validation set to be either Deal or Dalatt at each iteration of evolution. Therefore, NES-RE-O evolves the population without taking into account dataset shift, with Dshift only being used for the post-hoc ensemble selection step in line 9 of Algorithm 2
Following the discussion in Appendix B.4, recall that this is
As shown in the Figure 21 NES-RE-O shows minor improvement over NES-RE in terms of loss for ensemble size A/ 30 in the absence of dataset shift. This is in line with expectations, because evolution in NES-RE-S focuses on finding base learners which form strong ensembles for in-distribution data. On the other hand, when there is dataset shift, the performance of NES-RE-O ensembles degrades, yielding higher loss and error than both NES-RS and NES-RE. Nonetheless, NES-RE-O still manages outperform the DeepEns baselines consistently. We draw two conclusions on the basis of these results: (1) JES-RE-4 can be a competitive option in the absence of dataset shift. (2) Sampling the validation set, as done in NES-RE, to be Dral Dshift in line 4 of Algorithm 2 plays an important role is returning a final pool P of base learners from which ForwardSe lect can select ensembles robust to dataset shift.
23

---

Under review as a conference paper at ICLR 2021
M 5
M 10
M = 30
0.34
0.32
0.33
0.31
Deup2ra (DAATSS)
(deneeokeet)
0.32
0.30
NESSE
Deupdra (FS)
0.29
0.31
0.28
0.30
0.62
0.56
0.60
0.54
(severity
0.54
0.50
0.54
0.52
0.48
0.75
0.68
0.64
0.66
0.62
0.70
0.64
0.65
0.60
0.58
0.60
0.80
0.85
0.75
NLL
0.80
0.75
0.70
0.70
1.3
1.15
1.10
1.05
12
NL (severtyy
1.05
1.1
1.00
1.0
0.90
0.90
1.8
1.6
NLL (Severtyy
1.5
1.6
1.4
1.4
1.3-
1.3
100
200
300
400
100
200
300
400
100
200
300
400
Number networks evaluated
Number networks evaluated
Number networks evaluated
Figure 21: Results CIFAR-10 (Hendrycks & Dietterich 2019) with varying ensembles sizes M and shift severity. Lines show the mean NLL achieved by the ensembles with 95% % confidence intervals. See Appendix C.1.3 for the definition of NES-RE-O.
24

---

Under review as a conference paper at ICLR 2021
C.3 WHAT IF DEEP ENSEMBLES USE ENSEMBLE SELECTION OVER INITIALIZATIONS?
Recall that NES algorithms differ from deep ensembles in two important ways: the ensembles use varying architectures and NES utilizes ensemble selection (i.e. Forwardšelect applied to P) to pick the base learners. In this section, we conduct a study intended to investigate the following question: is the improvement offered by NES over deep ensembles only due to ensemble selection? In other words, we wish to isolate and understand the impact of varying architectures by comparing NES a baseline that also incorporates ensemble selection into the construction of deep ensembles.
Using the DARTS search space on Tiny ImageNet, we empirically compare NES to the baselines "DeepEns+ ES" which operate follows. We optimize a fixed architecture for the base learners, train K random initializations of it to form a pool and apply wwwaardSeeees to select an ensemble of size M from the pool. This yields the three additional baselines DeepEns + ES (DARTS/AmoebaNer/R) which correspond to optimizing the fixed architectures using the DARTS algorithm (DARTS), regularized evolution (AmoebaNet) and random search (RS).
The results indicate that NES outperforms or is at par with DeepEns + ES basclines, shown in Table 3 and Figure 22 In particular, both NES algorithms outperform DeepEns + ES (DARTS/AmoobaNee)) DeepEns+ ES (RS) is the most competitive of the deep ensemble baselines, which is improved upon by NES-RE and is competitive with NES-RS. Also, as expected, deep ensembles with ensemble selection consistently perform better than their counterparts without ensemble selection.
Table 3 also includes the computational costs of each method measured in terms of the number of networks trained. For each DeepEns ES baseline, we used a pool of size K 200 (as with NES) from which the ensemble is selected. This cost comes in addition to the cost of optimizing the fixed base learner architecture prior to forming the pool. For instance, the architecture for DeepLins + ES (RS) is optimized by random search, selecting the best architecture by validation loss from a random sample of K 200 (trained) architectures; this yields total cost of 400 networks trained. This is twice the cost of NES algorithms which required training 200 architectures to form the pool.
C.4 COMPARING NES TO ENSEMBLES WITH OTHER VARYING HYPEERPARAMETERS
Since varying the architecture in an ensemble improves predictive performance and uncertainty estimation demonstrated in Section [ it is natural to ask what other hyperparameters should be varied in an ensemble. It is also unclear which hyperparameters might be more important than others. Note that concurrent work by Wenzel al. 2020) has shown that varying hyperparameters such as L2 regularization strength. dropout rate and label smoothing parameter also improves upon deep ensembles. While these questions lie outside the scope of our work and left for future work, we conduct preliminary experiments to address them.
Tiny ImageNet
Tiny ImageNet
Tiny ImageNet
1.70
Deepfre tn (Amoehshetj
Deept (DAATS)
1.65
1.80
Oracle ensemble NLL
1.40
DecpEne (RSi
DeepEne-ES ES (Amoctatedd
Ensemble NLL
DeepErs ES (DARTS)
1.78
Docpers ES (RS)
1.60
1.20
NES-RE
1.76
Mts
1.55
1.74
1.00
1.50
1.45
1.70
0.80
10
15
10
15
5
10
15
Ensemble size (M)
Ensemble size (M)
Ensemble size (M)
Figure 22: Loss vs. ensemble size for NES and deep ensembles (with/without ensemble selection over initializations). The left plot shows that NES-RE outperforms all other methods across ensemble sizes. The right plot shows that ensembles produced by NES algorithms also consistently have higher diversity (as indicated by smaller oracle ensemble loss). See Appendix C.3 for details.
25

---

Under review as a conference paper at ICLR 2021
Table 3: A comparison of NES deep ensembles with ensemble selection over initializations for Tiny ImageNet over the DARTS search space with ensemble size M = 10. The computational costs are reports in terms of the number of networks trained (a typical network from this search space takes 3 hours to train on NVIDIA RTX 2080TT). The "arch" column indicates the number of architectures evaluated to find the architecture and the "ensemble" column indicates the number of architectures evaluated for building the ensemble. Note that for DARTS and AmoebaNet we convert the GPU hours for finding the architecture into number of networks trained by dividing by 3. See Appendix C.3 for details.
No dataset shift
Dataset shift (severity 5)
Cost (# nets trained)
Method
NLL
Classif. Error (%)
NLL
Classif. Error (%)
Arch.
Ensemble
DeepEns (DARTS)
1.59
39.08
3.75
71.58
DeepEns ES (DARTS)
1.57
38.68
3.68
70.90
32
200
DecpEns (AmochaNet)
1.55
38.46
3.76
71.72
25200
10
DeepEns + ES (AmochaNet)
1.54
38.12
3.70
71.68
25200
200
DeepEns (RS)
1.50
37.46
3.60=0.0z
70.48=o.ux
200
DcepEns ES (RS)
1.50
3.55
70.10
200
NES-RS
1.01
37.4210.91
3.53
69.931..a
200
NES-RE
1.48
36.982..57
3.55 on
70.22
200
In this section, we consider two additional baselines working over the DARTS search space on CIFAR-10/100:
1. HyperEns: Optimize fixed architecture, train K random initializations of it where the learning rate and L2 regularization strength are also sampled randomly and select the final ensemble of size M from the pool using ForwardSelesd ect. This is similar to hyper ens from Wenzel et al. (2020).
2. NES-RS (depth, width): As described in Appendix B.I NES navigates a complex (non- Euclidean) search space of architectures by varying the cell, which involves changing both the DAG structure of the cell and the operations at each edge of the DAG. We consider baseline in which we keep the cell fixed (the optimized DARTS cell) and only vary the width and depth of the overall architecture. More specifically, we vary the number of initial channels {12, 14, 16, 18, 203 (width) and the number of layers (5, 8, 11} (depth). We apply NES-RS -SS over this substantially simpler search space of architectures as usual: train K randomly sampled architectures (i.e. sampling only depth and width) form a pool and select the ensemble from it.
The results shown in Figures 23 and Table compare the two baselines above to DeepEns (DARTS), NES-RS and NES-RE As shown in Figure 23 NES-RE tends to outperform the baselines, though is at par with HyperEns on CIFAR-100 without dataset shift (Figure 23a). Under the presence of dataset shift (Figures 23b and 23c). both NES algorithms substantially outperform all baselines. Note that both HyperEns and NES-RR RS (depth, width) follow the same protocol as NES-RS and NES-RE: ensemble selection uses a shifted validation dataset when evaluating on shifted test dataset. In terms of classification error, the observations are similar shown in Table 4 Lastly, we view the diversity of the ensembles from the perspective oracle ensemble loss in Figure 24 As in Section 5 results here also suggest that NES agorithms tend to find more diverse ensembles despite having higher average base learner loss.
*Note that runs of DeepEns (DARTS), NES-RE and NES differ slightly this section relative to Section 5 as we tune the learning rate and Le regularization strength for each dataset instead of using the defaults used in Liu et al. (2019). This yields fair comparison: HyperEns varies the learning rate and Le regularization while using fixed, optimized architecture (DARTS), whereas NES varies the architecture while using fixed, optimized learning rate and T. regularization strength.
26

---

Under review as a conference paper at ICLR 2021
CPAR-20
OFAN-120
CIAA-10
CIAAI-20
OFAh-120
1.44
3.00
2120
Chamede MLL
0.25
3.00
C30
2.0
13
1.3
320
865
133
Irseemat Aee 100
Belenble
(a) No data shift
(b) Data shift (severity 3)
(c) Data shift (severity 5)
Figure 23: Plots show NLL vs. ensemble sizes comparing NES to the baselines introduced in Appendix C.4 CIFAR-10 and CIFAR-100 with and without respective dataset shifts (Hendrycks & Dietterich 2019).
Table 4: Classification errors comparing NES to the baselines introduced in Appendix C.4 for different shift severities and M = 10. Best values are bold faced.
Shift Severity
DARTS search space
Dataset
DeepEns (DARTS)
NES-RS (depth, width)
HyperEns
NES-RS
NES-RE
0
8.2
8.1
8.0
8.0
7.7
C10
3
25.9
25.0
24.1
22.5
21.5
5
43.3
40.8
42.1
38.1
34.9
0
28.8
28.1
28.8
28.4
28.4
C100
3
54.0
52.7
53.1
48.9
48.5
5
68.4
67.2
67.9
61.3
60.7
CIFAR-10
CIFAR-100
Average baseelerrer NLL
0.36
0.20
PspeCrr
Averge baceleareer NLL
1.24
Oracie enteembble NLL
0.18
NLL
0.60
0.15
NEZ tdeah. with
1.22
0.34
0.70
0.12
0.33
0.60
0.10
0.32
0.08
1.18
0.50
0.05
0.40
10
15
10
10
10
15
Ensemble size (M)
Ensemble size (M)
Ensemble size (M)
Ensemble size (M)
Figure 24: Average base leamer loss and oracle ensemble loss for NES and the baselines introduced in Appendix [..4 on CIFAR-10 10 and CIFAR-100 Recall that small oracle ensemble loss generally corresponds to higher diversity.
27


Reviews:
[{"review_id": "xLFjvlnHzfs", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes creating diverse ensembles of neural networks using an evolutionary method for finding base learners with high performance as well as mutual diversity. The selected base learners are then aggregated for an ensemble using a known method for ensemble selection. The paper is generally well written and addresses a relevant problem of constructing ensembles while training neural networks instead of building models first, independently, and later constructing ensembles. \n\nHaving said that, the paper lacks a significant contribution. The second phase (Ensemble Selection) of the proposed method is essentially the algorithm from Rich Caruana et al. 2004. The first phase of Pool Building suggests either a random generation or alternatively a vaguely described evolutionary method, lacking details or analysis.  It is not clear how exactly is the random initialization of architectures performed. Do you randomly select from a set of seed architectures or randomly create (i.e., random number of layers, random number of units, random activation functions, random initial weights, etc.)?\n\nGrowing from a random neural architectures to multiple highly performing (besides being mutually diverse) through single permutations upon model training and evaluation seems like an expensive process. An evolutionary approach in such a manner seems in efficient. Can you report the time taken for some of the reported cases in the evaluation? The ensemble methodology of unweighted averaging is fairly naive. What was the reason to select this one particularly? \n\nContribution #1 (page 2) isn't really a contribution. It is common knowledge amongst practitioners. The proposed method can lead to overfitting because the search seems to be based on a fixed set for evaluation. \n\nRegarding evaluation -- Can you explain how that is addressed? Have you evaluated your method on a broader variety of datasets? Can you confirm that the test data used for search/optimization is different than the one used for measuring reported performance? Did you consider comparing it other methods such as Tao 2019 (mentioned below) ?\n\nThis paper can improve its literature survey by citing more directly relevant work in ensemble search using diversification. Here are few examples of more sophisticated ensemble evolution work, not necessarily for a DL base learner, but relevant nonetheless:\n-Bhowan, et al. 2013. Evolving diverse ensembles using genetic programming for classification with unbalanced data. Trans. Evol. Comp\n-Khurana et al. 2018. Ensembles with Automated Feature Engineering. AutoML at ICML.\n-Olson et al. 2019. TPOT: A Tree-Based Pipeline Optimization Tool for Automating Machine Learning. Automated ML. \n-Tao, 2019. Deep Neural Network Ensembles. Machine Learning, Optimization, and Data Science. \n-Yao et al., 2008. Evolving artificial neural network ensembles, in IEEE Computational Intelligence Magazine\n\nOverall, it is a good problem, but this paper falls well short of the threshold.\nUpdate: I thank the authors for their response. Some justifications are provided and for that I will change my score. Overall, the paper still needs work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YS3Dmkchpti", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors addressed my concerns in the rebuttal. I have raised my score.\n\nSummary:\n\nThis paper combines AutoML techniques and deep ensembles to improve the ensemble diversity so that it improves the entire ensemble quality in both in- and out-of-distribution dataset. The authors made a study on two possible AutoML methods which can be combined with ensembles: 1. Random search & 2. Regularized mutation. The empirical results showed that the proposed NES methods outperform commonly selected baselines.\n\nPros:\n\nHow to improve ensemble diversity is one of the core topics on the way to better ensemble performance (in terms of both accuracy and uncertainty metrics). Many previous research works focused on 1. Build efficient ensembles while remaining reasonable diversity; 2. Improve ensemble diversity by exploring the hyper-parameter space. In practice, it is standard to ensemble neural networks with different depths or widths to improve diversity and hence the ensemble performance. However, as far as I know, there is no guidance or automatic mechanism in ensembling neural networks with different architectures. Thus, the problem this paper aims to tackle is significant and it will benefit the research community.\n\nThe authors did a self-contained introduction on ensembles & uncertainty and AutoML. The coverage on mutation AutoML is limited but this is still reasonable due to the page constraint. The motivation of why we want to combine AutoML and deep ensembles is clearly stated in section 3.2. Figure 1 demonstrates the effectiveness of various architectures in promoting ensemble diversity.\n\nThe empirical evaluation ranges across CIFAR dataset and ImageNet. It also includes calibration performance under dataset shift (uncertainty estimation on out-of-distribution dataset), which is the common benchmark to evaluate an ensemble's performance. The authors made comparisons to several reasonable baselines. The improvement of the proposed NES-RE/RS method over fixed architecture ensembles is consistent and significant. \n\n\nCons:\n\nFigure 1 demonstrates the motivation behind this work. To be more convincing, it can be supplemented with the predictive disagreement on the testset or the averaged KL divergence between the predictive distribution among ensemble members. Moreover,  the figure compares diversity between ensembles with different architectures and ensembles with random seeds. For a more comprehensive study, the figure can include a study on ensembles with different hyper-parameters. A more interesting baseline I will mention below is an ensemble with different depths. \n\nThe baselines considered in this paper only include ensembles with a fixed architecture. It would be more convincing if the authors can include other baselines which include ensembles with different architectures (without neural architecture search). For example, one naive baseline would be ensembling DeepEns(Optimal) with different depths (fully trained independently). This highlights the need for neural architecture search. It also helps to understand how much diversity in architecture (among ensemble members) we need in order to achieve desired diversity in ensemble predictions. Additionally, it is encouraged to compare to hyper-parameter ensembles. This uncovers the question of which axis (hyper-parameter & architectures) is more effective in promoting an ensemble’s performance.\n\nAnother missing part in this paper is the cost analysis of NES and how much does it increase compared to deep ensembles. Both NES-RS and NES-RE require training after sampling one neural architecture. This leads to a non-trivial computational overhead compared to traditional deep ensembles. \n\nIn section 4.3, it mentioned that a proportion of validation data encapsulates the belief about test-time shift. The authors didn’t mention whether the same protocol is applied to baselines (DeepEns). This leads to a question that is the improvement on out-of-distribution calibration coming from NES or shifted validation set. I consider this is a minor issue because Figure 21 in the appendix also shows that the clear improvement without shifted validation data.\n\nTable 1 shows that larger ensemble size leads to worse ensembling performance. This is against our general intuition in deep ensembles where more ensemble members lead to better performance. My guess is more ensemble members leads to optimization difficulties in NES. I expect to see more discussion on this observation.\n\nOverall, the authors propose a compelling solution to automatically design the neural network architectures in deep ensembels. However,  the cons slightly outweight the pros in this version.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DhNzkTAPqhx", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper suggests a new approach to the construction of ensembles of deep neural networks (DNN). Unlike previous methods which usually deal with multiple DNNs of same structure authors propose to form an ensemble of networks with different architecture. The main claim is that using diverse architectures increases diversity and hence the quality of predictions. To find the best architectures they use methodology inspired by neural architecture search (NAS) in particular random search and regularized evolution. The method for neural ensemble search (NES) is algorithmically simple although computationally hard. On several experiments the authors show NES outperforms standard deep ensembles formed from networks with same (even optimal) structure both in terms of test NLL and in terms of uncertainty estimation under domain shift.\n\nPros.\nNice idea\nSimple algorithm\n\n\nCons.\nMy main point for the criticism is the lack of experiment which I find to be crucially important namely the comparison aganist deep ensemble of DNNs with same architecture to which ForwardSelect procedure has been applied. Train P DNNs with same architecture then perform ForwardSelect routine to take the best K of them and compare your method with such deep ensemble. Currently the authors only compare their method with deep ensembles to which no special selection procedure was applied. This causes bias and it is not clear whether the improvement in NES is due to the usage of different architectures or due to the selection procedure which encourages diversity in resulting ensemble.\n\nP.S. Please correct me if I misunderstood the last point. I have read the corresponding part twice and found no evidence that you're using ForwardSelection when analysing the performance of ensembles of DNNs with same architecture.  \n\n====UPDATE===\nMy concerns were partly addressed in author's response so I have raised my score to 5.", "extra_scores": {}, "extra_text": {}}, {"review_id": "3qMs3dBfyrG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper explores whether one can use Architecture Search to enhance ensemble diversity. They start with the observation that embeddings generated by different architectures (for multiple different initialization per architecture) are well separated from each other. They then try out a couple of architecture search methods to find ensembles with diverse architectures that minimize the loss.\n\nWhile the novelty is incremental, I like the idea in general. My main objection is that critical baselines are not compared with. Ensemble diversity is a well explored topic with multiple easy to implement regularizations to increase diversity [1, 2, 3] and several more that should be compared with.\n\n[1] “Maximizing Overall Diversity for Improved Uncertainty Estimates in Deep Ensembles” by S Jain, G Liu, DK Gifford (AAAI 2020)\n[2] “Ensemble learning via negative correlation” by Y. Liu, X. Yao (Neural Networks 1999)\n[3] “Uncertainty in Neural Networks: Approximately Bayesian Ensembling” by Pearce et al (AISTATS 2020) ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new method to perform uncertainty estimation based on ensembles with diverse network architecture. 

The reviewers raised a few concerns:
- Although it is ok not to compare with (Tao, 2019), an active analytical comparison with baselines for ensemble diversification should not be overlooked e.g. (Yao et al, 2008), (Olson et al, 2019), (Khurana et al, 2018), etc.
- The approach presented in this paper is not novel in the general idea of searching for or diversifying ensembles 
- The reviewers agree that diversity methods can be implemented on top of NES, but it is unclear whether NES+diversity methods would give more over just diversity methods; so either measuring NES+diversity methods or a direct comparison of NES and diversity methods is important.

We encourage the authors address these issues in the next revision.

Decision: Reject