BPNAS: Bayesian Progressive Neural Architecture Search

Hyunwoong Chang * 1 Anirban Samaddar * 2 Sandeep Madireddy 2

Abstract

neuro-evolutionary and reinforcement learning, characterized by their exhaustive and combinatorial search strategies,
often face significant computational challenges. Differentiable NAS, however, marks a significant paradigm shift
in this field. By leveraging gradient-based optimization, it
substantially reduces computational load and enhances theefficiency and effectiveness of exploring the architectural
space. Pioneered notably by [6], this framework converts the
combinatorial optimization problem of NAS into a continuous one through weight sharing and continuous relaxation,a transformation that is crucial to applying gradient-based
methods. This streamlined approach in the architectural
search process not only accelerates the discovery but also facilitates the uncovering of more effective and efficient neuralnetwork architectures, showcasing the innovative potential
of Differentiable NAS in the realm of machine learning.

In the performance landscape of the multiple NAS
benchmarks, only a few operations contribute tohigher performance while others have detrimental effects. This motivates tailoring a posterior
distribution by imposing a higher prior quantity
on a sparser supernetwork to progressively prune
unimportant operations. Moreover, the Bayesian
scheme enables the straightforward generation ofarchitecture samples when provided with an estimated architecture from any NAS method. To that
end, we propose BPNAS, a Bayesian progressive
neural architecture search (NAS) method under
the differentiable NAS framework that combines
recent advances in the differentiable NAS framework with Bayesian inference adopting sparseprior on network architecture for faster convergence and uncertainty quantification in architecture search. With numerical experiments on the
popular NAS search space, we show that BPNAS
improves the accuracy and convergence speed
compared to state-of-the-art NAS approaches onbenchmark datasets.

In current NAS research, differentiable NAS methods showpromise but struggle with instability and generalization [7],[8]. Addressing these issues, probabilistic modeling, including Bayesian approaches and deep ensembling, offers
robustness and better uncertainty quantification [9]–[11].
However, their integration in differentiable NAS, as seen
in a few recent works [12]–[14], remains limited to learning point estimates of architecture and weight parameters.
Recently, Neural Ensemble Search (NES) has emerged, focusing on optimal ensembles of diverse networks rather
than single architectures, as explored in NESBS [15] andUraeNAS [16]. This approach improves accuracy and robustness but faces challenges in selecting architectures that
effectively curate a collection of architectures that function
cohesively as an ensemble. Random selection risks forming
less than optimal ensembles, undermining this approach’s
intended benefits.

1. Introduction
Neural Architecture Search (NAS) has emerged as a criticalfield in modern deep learning, focusing on automating thedesign of neural network architectures. This automation
addresses the challenges of manual design, which is laborious, resource-intensive, and requires significant expertise.
Rapid advancements in NAS, evidenced by a surge in research publications [1]–[3], have introduced methods suchas neuro-evolutionary algorithms, reinforcement learningbased algorithms, and differentiable architecture search approaches. These innovations have proven to be effective indiverse applications, such as computer vision [4] and natural
language processing [5]. Traditional NAS methods based on

The contributions of this paper are as follows:- We propose a unified framework, Bayesian Progressive
Neural Architecture Search (BPNAS) for architecture
search (NAS) and ensemble (NES) under the differentiable search schemes. The key concept involves
incorporating a sparse prior on the network structure,
progressively guiding any supernetwork structure towards a single architecture.

*

Equal contribution 1 Department of Statistics, Texas A&M
University, College Station, USA 2 Argonne National Lab, IL, USA.
Correspondence to: Sandeep Madireddy <smadireddy@anl.gov>.
Published at the 2 nd Differentiable Almost Everything Workshop
at the 41 st International Conference on Machine Learning, Vienna, Austria. July 2024. Copyright 2024 by the author(s).

- Our Bayesian framework naturally leads to operation
pruning algorithms for NAS and NES, similar to the1BPNAS: Bayesian Progressive Neural Architecture Searchbackward elimination procedure in linear regression.
Our algorithms ensure efficient model selection fromthe high-dimensional search space of architectures.
- We compare our framework against state-of-the-art
NAS and NES approaches on the popular NAS-Bench201 search space [17]. We empirically show that
BPNAS is more accurate with faster convergence thanthese approaches on CIFAR-10, CIFAR-100, andImageNet-16-120 datasets.

2. Background2.1. Landscape of the search space
Analyzing how performance varies among different architectural structures is crucial for developing a better algorithm. However, the analysis is exceedingly difficult due tothe complexity, for example, given the potential existenceof as many as 1018 candidates in the DARTS space [6].
As described in Section B in the appendix, NAS-Bench201 [17] enables us to glimpse the performance landscapeby evaluating the performance of each architecture on threedifferent datasets and providing some diagnostic information. It utilizes a cell-based search space, where a cell isrepresented by a densely connected directed acyclic graph(DAG) (V = [N ], E) by assigning a direction from thei-th node to the j-th node, if i < j for i, j ∈ [N ], where[N ] = {1, . . . , N } and every edge (i, j) ∈ E is associatedwith one of the elements o(i,j) of a predefined set of operations O. In NAS-Bench-201, the number of edges in E is 6
and the operation set contains 5 operations.

Figure 1. The figure shows box plots illustrating the distribution of
the accuracy for different architecture groups based on the Hamming distance from the highest accuracy architecture (the bestarchitecture) from NAS-Bench-201 dataset (CIFAR10). Each box
plot depicts the accuracy of architectures with a k-Hamming distance from the best architecture, for k = 1, . . . , 6. It indicates that
greater structural dissimilarity from the best architecture generally
results in lower accuracy.

the problem of selecting categorical operations into learning
continuous architecture mixing weights θ. The parameters
subject to optimization are two-fold: the network weightoo) where Wi,j
W = (Wi,jis the associated network weightparameter for an operation o in an edge e ∈ E, and thelatent architecture parameter α = (αe ) where αe is a parameter to define mixing weights θe = θe (αe ) ∈ ∆|O| .
There are variations for the function form, such as θe = αe([19]), θe = Softmax(αe ) ([6]), or θe = EDirichlet(αe ) (η)([12]). The bi-level objective L(α, W ) is to find the solution(α∗ , W ∗ ) satisfying

2.2. Differentiable architecture search for architecture
ensemble
As there are infinitely many possible architectures, it isnecessary to restrict the search space, opting not to search forcandidates from scratch. The prevalent approach involves
utilizing a cell-based search space defined in Section 2.1.
The whole architecture is then composed by stacking thesecells sequentially multiple times. The cell-based design, as
introduced by [18], markedly diminishes the complexity ofsearch spaces and has become widely adopted [1].

min Lval (α, W ∗ ) s.t. W ∗ = arg min Ltrain (α, W ). (1)αW

3. The proposed approach
We propose a unified Bayesian framework BPNAS for neural architecture search and its ensemble. The framework
not only facilitates the discovery of a single maximum aposteriori (MAP) architecture, but also enables uncertainty
quantification at the architecture structure level. Additionally, it provides an efficient neural ensemble search (NES)
scheme to sample a set of architectures, naturally enhancing
performance through model averaging.

Given the inherent difficulty in searching within a discrete
space, differential NAS has become the most widely adopted
method to address this challenge. DARTS [6] enables the efficient architecture search using a gradient-based optimizer
by employing a supernetwork of operations within eachPkedge. To be more specific, let ∆k = {z ∈ Rk : j=1 zj =space. we can1, zj ≥ 0 for j ∈ [k]} denote the k-simplex
Pdefine the output of j-th node xj = i<j ôi,j (xi ) whereP(i,j)
ôi,j (x) = k∈[|O|] θk ok (x) for θ ∈ ∆|O| where | · | denotes the cardinality of a set. This framework transforms

Let O the set of operations with |O| = nop . For simplicity, we assume that the candidate architectures contain
only one operation per edge. Let |E| = nedge , then wenhave total nopedge models in the search space. We define
the structure of (super)network as Γ = (γ1 , . . . , γnedge ),2

BPNAS: Bayesian Progressive Neural Architecture Searchwhere the nop vector γm = (γ1m , . . . , γnop m )T be the inclusion vector of operations for each m ∈ [nedge ], i.e.,for ` ∈ [nop ], γ`m = 1 means the supernetwork contains`-th operation in m-th edge, otherwise, γ`m = 0. Let
M = {Γ : kγm k0 = 1 for all m ∈ [nedge ]} be the setof the candidate architectures wherek·k0 denotes the L0
Pnedge0norm. We define dHD (Γ, Γ0 ) = m=11(γm 6= γm) for0Γ, Γ ∈ M as the Hamming distance, which indicates thenumber of different edges between Γ and Γ0 . We define
1n,n0 (resp. 1n ) as the n × n0 matrix (resp. n vector) whose
elements are all one, and let 1 be an indicator function.

Pruning criterion For m-th edge with kγm k0 > 1, we
prune an operation ifθ(αm ) ∈/ Bδ (c),where Bδ (c) = {r ∈ Rkγm k0 : kr − ck2 ≤ δ}, k·k2 denotes the L2 norm, and c = 1kγm k0 /kγm k0 is the center of∆kγm k0 . In our experiments, we have considered θ(αm ) asa random sample drawn from Dirichlet(αm ). Intuitively,
the criterion implies pruning if the current architecture mixing weights of the supernetwork deviate too far away (controlled by δ) from a uniform distribution. This is analogous
to the backward elimination procedure [22], where the algorithm starts with all operations on all edges and then decides
which operation to keep on each edge for the architectureby sequentially excluding the others.

We can rewrite the bi-level objective function (1) as
L(α, W ) = L(α(Γ), W (Γ)|Γ = 1nedge ,nop ),since the supernetwork structure remains intact throughout
the training. By using (1), given the above form of L , wedefine the conditional posterior distribution on (α, W )π(α, W |Γ) ∝ e−L(α(Γ),W (Γ)|Γ) ,Algorithm 1 Bayesian Progressive Architecture search(BPNAS)
Input: An initial supernetwork Γ with architecture parameters α and weights W , posterior distribution
π(W, α, Γ), and a threshold δwhile kγm k0 > 1 for some m do(2)

as a Gibbs distribution. Putting the prior on
nedge

nedge

π(Γ) ∝Ym=1

π(γm ) =Y

e−ckγm k0 1{|γm |>0} (γm ),Update W, α by stochastic gradient descent.
1kγm k0
if kθ(αm ) − kγ
k2 ≥ δ then
m k0

m=1

the posterior distribution is defined asπ(α, W, Γ) ∝ π(α, W |Γ)π(Γ).

Select (`, m) = arg min{(`0 ,m0 ):Γ`0 m0 =1} α`0 ,m0and set Γ`m = 0.
Reset α.
Output: An architecture Γ with a single operation for each
edge.

(3)

Note that the prior enforces the sparsity in the supernetwork to eventually find one of the candidate architecturesΓ ∈ M as one of the modes with one operation peredge. This can be done by choosing c sufficiently large,
π(α, W, Γ) ≤ π(α0 , W 0 , Γ0 ) if kΓk0 > kΓ0 k0 , so thatmodes of the distribution can be formed at M. Therefore,
the objective is to find a single architecture Γ̂MAP ∈ M
where

Sampling architectures for ensemble One prominent
advantage of this framework is an efficient method to sample
a set of architectures given one architecture Γ̂ ∈ M fromany NAS algorithms. For a predefined number q ∈ [nedge ],we let Sq be a set of q numbers randomly sampled from[nedge ] and define the reconstructed supernetwork Γ̂recon as(
1nop , if m ∈ Sq ,
recon
γ̂m
=
γ̂m ,
otherwise,(α̂MAP , Ŵ MAP , Γ̂MAP ) = arg max π(α, W, Γ).
α,W,Γ

Finding a solution from π(α, W, Γ) is hard since the posterior distribution is a joint distribution of discrete and continuous variables, and the continuous parameters α, W depend on the discrete parameter Γ. It is necessary to devise
efficient movement between different dimensional spaces.
Note that this setup is commonly associated with reversible
jump Markov chain Monte Carlo (MCMC) algorithms [20],which are commonly applied to Bayesian model selection
problems, although we are only interested in finding a MAP
estimate of Γ. Among many ways to construct these jumps
and automate the process, we propose an efficient algorithm
that prunes less important operations progressively after asufficient amount of time for training the continuous variables α(Γ) and W (Γ) until we obtain a single network inM.

which reconstructs supernetworks partially for some edges.
We run Algorithm 1 with Γ̂recon as the initial supernetwork.
The final output Γ̃ from the procedure is at most q-Hamming
distance away from the given architecture Γ̂. We empiricallyfind that the performance of the architecture is similar tothat of the given architecture, probably due to its structuralsimilarity (Figure 1). We repeat this procedure N times tocurate an ensemble of well-performing architectures. Note
that, since each repetition initializes only a partial supernetwork, this procedure is less memory intensive and can be
efficiently parallelized.
3

BPNAS: Bayesian Progressive Neural Architecture Search
Methods
ResNet [21]DrNAS [12]BPNAS
OptimalCIFAR-10
test
epochs93.97
100
94.36 ± 0.00
100
94.26 ± 0.22
70
94.37
-

validation
70.42
70.25 ± 1.53
73.38 ± 0.23
73.49

CIFAR-100
test
70.86
71.00 ± 1.27
73.40 ± 0.19
73.51

epochs
100
100
50
-

ImageNet-16-120
validation
test
44.53
43.63
46.37 ± 0.00 46.34 ± 0.00
46.37 ± 0.00 46.34 ± 0.00
46.77
47.31

epochs
100
100
26
-

Table 1. Performance compared to the state-of-the-art methods on NAS-Bench-201.On the CIFAR-10 and ImageNet, BPNAS performs
similarly to DrNAS; however, it outperforms DrNAS on the CIFAR-100. On all datasets, BPNAS significantly reduces the computational
cost of the architecture search.

Methods
NES-RS [9]NESBS [15]BPNAS

Cifar-10
94.17 ± 0.33
94.08 ± 0.07
95.10 ± 0.07

CIFAR-100
74.42 ± 0.84
75.00 ± 0.17
77.47 ± 1.04

ImageNet-16-120
45.66 ± 1.67
47.32 ± 0.35
50.27 ± 0.45

Table 2. Comparison of performances of the state-of-the-art NES methods on NAS-Bench-201. For all datasets, BPNAS outperforms allother methods.

4. Experiments

across replications. For the other methods, the default number of epochs was set at 100 across all datasets. We observethat across all datasets, BPNAS significantly reduces computational time without any significant detrimental effecton classification performance, notably requiring 70% fewer
epochs on ImageNet-16-120.

In this section, we describe the experiments conducted to
study both the efficiency and effectiveness of BPNAS in
the popular NAS search space: the NAS-Bench-201 [17].
In this search space, we compare the BPNAS architecture
search algorithm (Algorithm 1) with the state-of-the-art
NAS algorithms [12], and the BPNAS ensemble algorithm
is compared with the state-of-the-art NES algorithms [15].
We compare these methods on CIFAR-10, CIFAR-100, andImageNet-16-120 datasets.

4.2. Ensemble results
In Table 2, we compare BPNAS with state-of-the-art NES
methods on the three datasets. We present the mean test
accuracies and standard deviations of the BPNAS algorithmwith an ensemble size of 3, as well as those of the twomost recent NES methods [15]. For each BPNAS ensemble,
we set the number of perturbed edges q = 1 for the initialsupernetwork.

4.1. Architecture search results
Table 1 presents the mean accuracies of the NAS methods across 10 seeds on the three datasets, along with thestandard deviations. We also report the accuracies of a baseline ResNet network [21] and the highest accuracy attained
among all architectures from the NAS-Bench-201 database.
In all the datasets, We observe that BPNAS can find architectures that perform similarly to the optimal architecturein NAS-Bench-201, with a gap of less than 1%. As DrNAS [12] has been reported as the state-of-the-art method,
we compare its performance with BPNAS. While BPNAS
performs similarly to DrNAS on CIFAR-10 and ImageNet,
it outperforms DrNAS on CIFAR-100 by more than 2% inaverage accuracy.

BPNAS ensembling achieves the highest test accuracy
across all datasets, significantly outperforming the other
NES methods. By setting q small, the algorithm quickly
converges to a candidate architecture for the ensemble. In
addition, the BPNAS ensembling approach builds upon anarchitecture generated by any NAS algorithm; in our case,
we use Algorithm 1, making it efficient in finding a set ofcandidates for the ensemble.

5. Discussion

One of the key properties of BPNAS is the pruning criterion
described in the previous section which prunes the less important operations from the edges of the cell as the training
progresses. The amount of pruning applied is controlled
through the parameter δ which we treat as a hyperparameter.
The setting of δ is done by maximizing the accuracy andspeed of convergence of Algorithm 1 on the validation set.
More details are presented in Appendix C.

In this paper, we propose BPNAS, a Bayesian frameworkfor fast exploration and uncertainty quantification of theneural architecture search space. A pruning procedure is
proposed to sample well-performing architectures from theposterior distribution. The experiments demonstrate the efficacy of BPNAS, revealing improved efficiency and accuracy
compared to the state-of-the-art NAS and NES methods onbenchmark datasets. It would be interesting to extend ourframework by incorporating uncertainty in edge weights
and biases, potentially further improving accuracy.

In Table 1, we report the average number of epochs it took
for BPNAS to arrive at a final architecture on each data set
4

BPNAS: Bayesian Progressive Neural Architecture Search

References
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

C. White, M. Safari, R. Sukthanker, B. Ru, T. Elsken, A.
Zela, D. Dey, and F. Hutter, “Neural architecture search: Insights from 1000 papers,” arXiv preprint arXiv:2301.08727,
2023.
D. Baymurzina, E. Golikov, and M. Burtsev, “A reviewof neural architecture search,” Neurocomputing, vol. 474,
pp. 82–93, 2022.
P. Ren, Y. Xiao, X. Chang, P.-Y. Huang, Z. Li, X. Chen,
and X. Wang, “A comprehensive survey of neural architecture search: Challenges and solutions,” ACM Computing
Surveys (CSUR), vol. 54, no. 4, pp. 1–34, 2021.
J.-S. Kang, J. Kang, J.-J. Kim, K.-W. Jeon, H.-J. Chung,and B.-H. Park, “Neural architecture search survey: A computer vision perspective,” Sensors, vol. 23, no. 3, p. 1713,
2023.
N. Klyuchnikov, I. Trofimov, E. Artemova, M. Salnikov,
M. Fedorov, A. Filippov, and E. Burnaev, “Nas-bench-nlp:
Neural architecture search benchmark for natural language
processing,” IEEE Access, vol. 10, pp. 45 736–45 747,
2022.
H. Liu, K. Simonyan, and Y. Yang, “Darts: Differentiablearchitecture search,” arXiv preprint arXiv:1806.09055,
2018.
A. Zela, T. Elsken, T. Saikia, Y. Marrakchi, T. Brox, and F.
Hutter, “Understanding and robustifying differentiable architecture search,” arXiv preprint arXiv:1909.09656, 2019.
X. Chen and C.-J. Hsieh, “Stabilizing differentiable architecture search via perturbation-based regularization,” in International conference on machine learning, PMLR, 2020,
pp. 1554–1565.
S. Zaidi, A. Zela, T. Elsken, C. C. Holmes, F. Hutter, and
Y. Teh, “Neural ensemble search for uncertainty estimation and dataset shift,” Advances in Neural Information
Processing Systems, vol. 34, pp. 7898–7911, 2021.
M. Chen, J. Fu, and H. Ling, “One-shot neural ensemble
architecture search by diversity-guided search space shrinking,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 16 530–
16 539.
A. R. Narayanan, A. Zela, T. Saikia, T. Brox, and F. Hutter, “Multi-headed neural ensemble search,” arXiv preprint
arXiv:2107.04369, 2021.
X. Chen, R. Wang, M. Cheng, X. Tang, and C.-J. Hsieh,“Drnas: Dirichlet neural architecture search,” arXiv preprint
arXiv:2006.10355, 2020.
H. Zhou, M. Yang, J. Wang, and W. Pan, “Bayesnas: Abayesian approach for neural architecture search,” in International conference on machine learning, PMLR, 2019,
pp. 7603–7613.
M. Zhang, S. Pan, X. Chang, S. Su, J. Hu, G. R. Haffari, and B. Yang, “Balenas: Differentiable architecture
search via the bayesian learning rule,” in Proceedings ofthe IEEE/CVF Conference on Computer Vision and Pattern
Recognition, 2022, pp. 11 871–11 880.
Y. Shu, Y. Chen, Z. Dai, and B. K. H. Low, “Neural ensemble search via bayesian sampling,” in Uncertainty in
Artificial Intelligence, PMLR, 2022, pp. 1803–1812.
S. Premchandar, S. Madireddy, S. Jantre, and P. Balaprakash, “Unified probabilistic neural architecture andweight ensembling improves model robustness,” arXiv
preprint arXiv:2210.04083, 2022.

[18]

[19]

[20]

[21]

[22]
[23]

[24]

[25]

[26]

[27]

[28]

5

X. Dong and Y. Yang, “Nas-bench-201: Extending thescope of reproducible neural architecture search,” arXiv
preprint arXiv:2001.00326, 2020.
B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, “Learningtransferable architectures for scalable image recognition,”in Proceedings of the IEEE conference on computer visionand pattern recognition, 2018, pp. 8697–8710.
L. Li, M. Khodak, M.-F. Balcan, and A. Talwalkar,“Geometry-aware gradient algorithms for neural architecture search,” arXiv preprint arXiv:2004.07802, 2020.
P. J. Green, “Reversible jump markov chain montecarlo computation and bayesian model determination,”
Biometrika, vol. 82, no. 4, pp. 711–732, 1995.
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE
conference on computer vision and pattern recognition,
2016, pp. 770–778.
M. A. Efroymson, “Multiple regression analysis,” Mathematical methods for digital computers, pp. 191–203, 1960.
X. Chu, T. Zhou, B. Zhang, and J. Li, “Fair darts: Eliminating unfair advantages in differentiable architecture search,”
in European conference on computer vision, Springer,
2020, pp. 465–480.
G. Li, G. Qian, I. C. Delgadillo, M. Muller, A. Thabet, andB. Ghanem, “Sgas: Sequential greedy architecture search,”
in Proceedings of the IEEE/CVF Conference on Computer
Vision and Pattern Recognition, 2020, pp. 1620–1630.
H. Liang, S. Zhang, J. Sun, X. He, W. Huang, K.
Zhuang, and Z. Li, “Darts+: Improved differentiable architecture search with early stopping,” arXiv preprint
arXiv:1909.06035, 2019.
X. Chen, L. Xie, J. Wu, and Q. Tian, “Progressive differentiable architecture search: Bridging the depth gap between
search and evaluation,” in Proceedings of the IEEE/CVF international conference on computer vision, 2019, pp. 1294–
1303.
S. Yan, Y. Zheng, W. Ao, X. Zeng, and M. Zhang, “Doesunsupervised architecture representation learning help neural architecture search?” Advances in neural information
processing systems, vol. 33, pp. 12 486–12 498, 2020.
R. Ardywibowo, S. Boluki, X. Gong, Z. Wang, and X.
Qian, “Nads: Neural architecture distribution search for
uncertainty awareness,” in International Conference on
Machine Learning, PMLR, 2020, pp. 356–366.

BPNAS: Bayesian Progressive Neural Architecture Search

A. Related Works
Differentiable NAS In the landscape of Differentiable NAS, recent efforts have concentrated on overcoming the collapse
problem in DARTS [6], with various methodologies emerging. FairDARTS [23] mitigates exclusive competition using thesigmoid function, while SGAS [24] adopts a greedy strategy. DARTS+ [25] and Progressive DARTS [26] employ early
stopping to regulate identity operations. While approaches like FairDARTS, SGAS, DARTS+, and Progressive DARTS
offer some remedies, they often require significant human intervention and struggle with flexibility and task transferability.
Innovations such as Hessian eigenvalues as indicators [7] and unsupervised representation learning [27] address these issues
to some extent. However, distribution-based methods [12]–[14] present more effective solutions. DrNAS [12], for instance,
formulates differentiable NAS as a distribution learning problem using Dirichlet distribution, optimizing it with pathwise
derivative estimators and a distance regularizer for stability and generalization. BaLeNAS [14] tackles the instability with
Bayesian Learning and NGVI, enhancing exploration and stability. BayesNAS [13] adopts a Bayesian approach, using
hierarchical automatic relevance determination priors to ensure sparsity and interconnectedness in the pruned network
structure. These methods collectively signify a shift towards more stable, explorative, and effective architecture searchtechniques in NAS. However, these works only learn a point estimate of the architecture and weights, so additional propertiesof distributional formulation such as uncertainty quantification, ensembling, or robustness have not been explored.
Neural Ensemble Search In the realm of Neural Ensemble Search (NES), various methodologies have been developed
to optimize ensembles of neural networks. NES-RS [9] introduced a technique that uses random search and regularized
evolution, achieving enhanced accuracy and robustness, albeit with considerable computational demands. MH-NES [11]proposed a Multi-headed NES approach that applies differentiable NAS to multi-headed networks, optimizing ensemble
loss and promoting diversity among predictions, thereby reducing computational intensity. NESBS approach [15] utilizeda supernetwork to estimate ensemble performance, incorporating Bayesian sampling for efficient selection. Similarly,
NADS [28] employed an evolutionary search with a focus on improving uncertainty estimates and out-of-distribution
detection, demonstrating the growing versatility and sophistication of NES strategies.

B. NAS-Bench-201 space
The NAS-Bench-201 database contains 15,625 pre-trained models with varying cell architectures on CIFAR-10, CIFAR-100,
and ImageNet-16-120 datasets. Given an architecture, we can query this database to get the final accuracy and thus savetime for running the expensive evaluation stage for any NAS method. Therefore, this database enables us to separately
compare the architecture search phase and the evaluation phase of the NAS algorithms.

(a)

(b)

Figure 2. The effect of δ0 on the accuracy of the architecture selected by the BPNAS algorithm 1 on NAS-BENCH-201 search space for
CIFAR-10 and CIFAR-100. It is observed that lower δ0 leads to lower accuracy and higher instability in the results.

C. On hyperparameter δ
In Algorithm 1, the pruning criterion depends on the hyperparameter δ. This hyperparameter controls how fast the algorithm
proposes a candidate architecture.In our implementation, we considered δ as the 95-th percentile value of the distribution of
6

BPNAS: Bayesian Progressive Neural Architecture Search
1kγm k0
the random variable kDirichlet(δ0 1kγm k0 ) − kγ
k2 for some m. Therefore, increasing δ or equivalently δ0 results in
m k0

1

kγm k0more aggressive pruning as the Dirichlet(.) distribution becomes increasingly dense around its mean kγ. In Section 4,
m k0
we presented the experimental results for a single δ0 value. In this section, we explore the sensitivity of the results withchanging δ0 .

In Fig. 2, we plot the mean accuracy across 10 seeds (with the standard deviations) against four δ0 values on CIFAR-10
and CIFAR-100. We observe that lower δ0 on these datasets resulted in higher standard deviation and lower accuracy on
both the test and validation set. In the experiments, we found the accuracy on ImageNet-16-120 to be insensitive to thehyperparameter δ0 .

7