Robustifying and Boosting Training-Free Neural Architecture Search
Authors: Zhenfeng He
Yao Shu
Zhongxiang Dai
Bryan Kian Hsiang Low
Venue: ICLR 2024 poster (2024)
Keywords: Neural Architecture Search
Training-free NAS
Bayesian Optimization
Precision@K
Partial Monitoring
Primary area: general machine learning (i.e., none of the above)
TL;DR: The paper proposes a new NAS algorithm RoBoT to robustify existing training-free NAS and further boost them.

Abstract: Neural architecture search (NAS) has become a key component of AutoML and a standard tool to automate the design of deep neural networks. Recently, training-free NAS as an emerging paradigm has successfully reduced the search costs of standard training-based NAS by estimating the true architecture performance with only training-free metrics. Nevertheless, the estimation ability of these metrics typically varies across different tasks, making it challenging to achieve robust and consistently good search performance on diverse tasks with only a single training-free metric. Meanwhile, the estimation gap between training-free metrics and the true architecture performances limits training-free NAS to achieve superior performance. To address these challenges, we propose the robustifying and boosting training-free NAS (RoBoT) algorithm which (a) employs the optimized combination of existing training-free metrics explored from Bayesian optimization to develop a robust and consistently better-performing metric on diverse tasks, and (b) applies greedy search, i.e., the exploitation, on the newly developed metric to bridge the aforementioned gap and consequently to boost the search performance of standard training-free NAS further. Remarkably, the expected performance of our RoBoT can be theoretically guaranteed, which improves over the existing training-free NAS under mild conditions with additional interesting insights. Our extensive experiments on various NAS benchmark tasks yield substantial empirical evidence to support our theoretical results.

Published as a conference paper at ICLR 2024
ROBUSTIFYING AND BOOSTING TRAINING-FREE NEURAL ARCHITECTURE SEARCH
Zhenfeng He!, Yao Shu²; Zhongxiang Dai Bryan Kian Hsiang Low!
DDepartment of Computer Science, National University of Singapore
?Guangdong Lab of Al and Digital Economy (SZ)
'Laboratory for Information and Decision Systems, Massachusetts Institute of Technology he zhen nus edu, aamu ac. en, daizx@mit edu, lowkhê comp. nus. edu.
ABSTRACT
Neural architecture search (NAS) has become a key component of AutoML and a standard tool to automate the design of deep neural networks. Recently, training- free NAS as an emerging paradigm has successfully reduced the search costs standard maining-based NAS by estimating the true architecture performance with only training-fiee frre metrics. Nevertheless, the estimation ability of these metrics typically varies across different tasks, making it challenging to achieve robust and consistently good search performance on diverse tasks with only a single training- free metric. Meanwhile, the estimation gap between training-free free metrics and the true architecture performances limits training-free NAS to achieve superior per- formance. To address these challenges, we propose the robustifying and boosting training-free NAS (RoBo'I) algorithm which (a) employs the optimized combi- nation of existing training-free free metrics explored from Bayesian optimization develop a robust and consistently better-performing metric on diverse tasks, and (b) applies greedy search, i.e., the exploitation, on the newly developed metric bridge the aforementioned gap and consequently to boost the search performance standard training-free NAS further. Remarkably, the expected performance of our RoBo'T can be theoretically guaranteed, which improves over the existing training-free free NAS under mild conditions with additional interesting insights. Our extensive experiments on various NAS benchmark tasks yield substantial empiri- cal evidence to support our theoretical results. Our code has been made publicly available hhtttp:: //tpttgtttbtttt/// www.uuu...oom//oao wommhhiit f1 1174/RoBoT
INTRODUCTION
In recent years, deep learning has witnessed tremendous advancements, with applications ranging from computer vision (Caelles al. 2017) to natural language processing (Vaswani et al.) 2017). These advancements have been largely driven by sophisticated deep neural networks (DNNs) like AlexNet (Krizhevsky al. 2017). VGG (Simonyan & Zisserman 2014), and ResNet (He et al., 2016), which have been carefully designed and fine-tuned for specific tasks. However, crafting such networks often demands expert knowledge and significant amount of trial and error. To mitigate this manual labor, the concept of neural architecture search (NAS) was introduced, aiming to auto- mate the process of architecture design. While numerous training-based NAS algorithms have been proposed and have demonstrated impressive performance (Zoph & Le 2016 Pham et al., 2018), they often require significant computational resources for performance estimation, as entails train- ing DNNs. More recently, several training-free metrics have been proposed to address this issue (Mellor et al. 2021 Abdelfattah et al. 2020; (Shu et al. (02T). These metrics are computed with at most forward and backward pass from single mini-batch of data, thus the computation cost can be deemed negligible compared with previous NAS methods, hence training-free.
However, there are two questions that still need to be investigated. While training- frree metrics have demonstrated promising empirical results in specific, well-studied benchmarks such as NAS-
"Coreeponding author.

---

Published as a conference paper at ICLR 2024
Bench-201 (Dong & Yang 2020). recent studies illuminated their inability to maintain consistent performance across diverse tasks (White et al., 2022). Moreover, as there is an estimation gap between the training-frees metrics and the true architecture performance, how to quantify and bridge this gap remains an open question. We elaborate on the details of these questions in Section 3
To address the questions, we propose robustifying and boosting training-fres neural architecture search (RoBoT). We explain the details of RoBoT in Section 4 First, we use a weighted linear com- bination of training-free metrics propose new metric with better estimation performance, where the weight vectors are explored and optimized using Bayesian optimization (BO) (Section 4.1 4.2) Second, we quantify the estimation gap of the new metric using Precision value and then bridge the gap with greedy search. By doing so, we exploit the new metric, hence boosting the expected performance of the proposed neural architecture (Section 4.3)
To understand the expected performance of our proposed algorithm, we make use of the theory from partial monitoring (Bartók et al. 2014 Kirschner et al., 2020) to provide theoretical guarantees for our algorithm (Section 5). To the best of our knowledge, we are the first to provide bounded expected performance of a NAS algorithm utilizing training-free metrics with mild assumptions. We also discuss the factors that influence the performance. Finally, we conduct extensive experiments to ensure that our proposed algorithm outperforms other NAS algorithms, and achieves competitive or even superior performance compared to any single training-free ffree metric with the same search budget and use ablation studies to verify our claim (Section 6).
2 RELATED WORK
Training-free NAS Recently, several training-free metrics have emerged, aiming to estimate the generalization performance of neural architectures. This advancement allows NAS to bypass the model training process entirely. For example, MeannleeeMllorrr et al. (02T]) introduced a heuristic metric that leverages the correlation of activations in an initialized DNN. Similarly, Abdelfattah et al. (2020) established a significant correlation between previously employed training-free metries in network pruning. such as snip, grasp and synflow. Ning et al.] (202I) demonstrated that even simple proxies like params and flops possess significant predictive capabilities and serve as baselines for training- free metrics. Despite these developments, |White et al. (2022) noted that existing training-free metric consistently outperforms others, emphasizing the necessity for more robust results.
Hybrid NAS A few initial works have sought to combine the training- free metries information and training-based searches. Some methods, such as OMNI (White er al.) (021b) and ProxyBO (Shen) al. 2023). employ a model-based approach, utilizing training- ffree metrics as auxiliary information to enhance their estimation performance. However, requiring modeling of the search space limits the flexibility when these methods are applied to diverse tasks, and the effectiveness of these methods is questionable when applied to new search space. Moreover, a comprehensive theoretical analysis regarding the influence of training- free metrics on their results is currently absent. Furthermore, (Shu eet al. (2022b) directly boosts the performance of the tradient-based training-fic frree metric. but their focus is confined to the enhancement of a single training- free metric, and thus is still subject to the instability inherent to individual training- ffree metrics.
3 OBSERVATIONS AND MOTIVATIONS
Although training- free NAS has considerably accelerated the search process of NAS via estimating the architecture performance using only training-free metrics, recent studies have widely uncovered that these metrics fail to perform consistently well on different tasks (White et al.) 2022). To illustrate this, we compare the performance of list of training-free metrics on various tasks TransNAS- Bench-100 101-micro (Duan et al. 2222I) as shown in Table [ The results show that single training- free metric can consistently outperform the others, emphasizing the demand for achieving robust and consistent search results based training- free metrics. Therefore, it begs the first research question RQI: Can we robustify existing training-free free metrics to make them perform consistently well on diverse tasks?
The conventional approach to propose a neural architecture using training-free free metrics involves selecting the architecture with the highest score. However, this method is potentially limited due
2

---

Published as a conference paper at ICLR 2024
Table 1: Validation ranking of the highest-score architecture for each training-free metric (the value before comma), and the ranking of the best-performing architecture on each training- metric (the value after comma) on MunnNAA--Bech--O1--iae
(4,096 architectures).
Metrics
Scene
Object
Jigsaw
Segment.
Normal
grad norm (Abdelfattah et al. 2020
961, 862
2470. 1823
3915, 1203
274, 738
2488, 1447
snip (Lee al.. 2019
2285, 714
2387, 1472
2701,
951, 682
2488, 15811
grasp Wang et al. 2020
372, 3428
3428, 2922
2712
2855, 1107
665, 680
fisher [Tumer cf al. 20%))
2286, 11.50
2470, 1257
2701, 1582
3579, 1715
4015, 1761
synllow Tanaka et al. 2020
509, 258
1661, 50
1691. 760
n/a
n/a
jacob_cov (Mellor et a
2021
433, 1207
2301, 2418
441, 1059
592, 323
205, 2435
naswol (Mellor et al. 2021
2130, 345
1228, 1466
2671, 626
709, 1016
442, 1375
zen (Lin at. 2021
509,106
1661, 598
2552, 430
830, 909
442, 1002
params flops
773,
2387,
494
830, 1008
310, 1251
773, 366
2387, 427
231, 497
830, 997
310, 1262
to the estimation gap in using training-free metrics to estimate the true architecture performance: There could be superior architecture within the top-ranked segment of the training-free metric that does not necessarily possess the highest score. For instance, the results displayed in Table [] demonstrate that the highest-score architecture proposed by the synflow metric for the Object task performs poorly. However, the optimal architecture within the entire search space can be identified by merely conducting further searches among the top 50 architectures. Despite these findings, no existing studies have explored the extent of this potential, or whether allocating search budget to exploit training-free metrics would yield valuable results. Therefore, our second research question arises: RQ2: After the development of our robust metric, how we quantify such estimation gap and propose a method to bridge this gap for further boosted NAS?
4 OUR METHODOLOGY
To address the aforementioned questions, we will use this section elaborate on the method RoBoT we propose. Consider the search space set of N neural architectures, i.e., A ] where each architecture A has a true architecture performance f(AA based on the objective evaluation metric f. Without loss of generality, we assume larger value of is more desirable. Alternatively, the entire search space has been assessed by the objective evaluation metric f. we can sort their performance and obtain the rankings regarding as R2 (A), where Ry (.4) 1 indicates A is the optimal architecture. We also have a set of M training-free metrics MI = JMM where larger value of (A) suggests A is more favorable by M₁. Notice that we define the search costs as the number of times querying the objective evaluation metric, the computation costs of training-free free metrics are negligible to the objective evaluation metric, given that the latter usually involves the training process of neural architectures. The goal of NAS is to find the optimal architecture with the search costs T.
4.1 ROBUSTIFYING TRAINING-FRES NAS METRIC
As discussed in RQ1, training-free metrics usually fail to perform consistently well across various tasks. To robustify them, we propose using an ensemble method to combine them, as ensemble meth- ods are widely known tool to achieve consistent performance (Zhoul 2012 Shu et al.) (022a)). We choose weighted linear combination as the ensemble method and discuss other choices in Ap- pendix C Formally, define the weighted linear combination estimation metric with weight vector as M(A w) E (AA). To find the optimal architecture, we need identify the most suitable weight vector w" as
w = arg max (A((w), s.t. A(w) A arg max M(A; w)
Subsequently, we propose At = A(w"), which represents the best architecture we can obtain based on the information of training-free metrics M. using the weighted linear combination.
3

---

Published as a conference paper at ICLR 2024
Metric
Metric 2
Architecture
0.05
0.9
Architecture
1
0
Architecture
0.04
0.95
Architecture
Weghh aTMeSICA
Antiaeraadd
(a)
(b)
Figure I: (a) Training-fre free Metric and 2's scores for four architectures for a specific task, higher value indicates more recommended. The true architecture performance is ranked as 1 > 2 > 3 >> 4. (b) The highest-scoring architecture selected based on the weight vector of Metric and Metric 2. Each region of the weight vector selects the same architecture, as represented by its color.
The rationale for opting for a linear combination stems from two key aspects. First, the linear com- bination has superior representation ability compared with training-free metrics, where the lower bound can be observed from the one-hot setting of the weight vector (i.e., the weight of the best training- free metric is 1 and the rest are 0). Furthermore, Proposition [ (prove Appendix (A.1) suggests that linear combination of two estimation metrics can almost always improve the correla- tion with the objective evaluation metric, and the exception exists rare cases such as training-free metrics are co-linear.
Proposition 1. Suppose there are two estimation metrics MI, M2. and objective evaluation metric f. If Cov[M1, * fonMM,./Vaa/MM, and Cov[M1, + Covi ff Mar Bwi, E IR Cov[Ma..]
Cov[Ma.))
such that
Peaasson (w Mi + w2M2, > (ax(prranson (M1, f), PPearson (M2, (M
where Cov Y}, Prearson X, Y) are the covariance and Pearson's 's correlation between X and Y, respectively, and Var [X] is the variance of X.
This claim be extended to the scenario of combining multiple metrics, which can be initially treated as a linear combination two metrics, and then combined with third. In this context, the strictly increasing properties almost always hold. Hence, Proposition iimplis that the architecture proposed by a linear combination could outperform any architecture proposed by single metric.
The second rationale is that linear combinations have sufficient expressive hypothesis space, which means improved performance can be obtained from the hypothesis space but it may not be too complex be optimized. To clarify, the hypothesis space here refers to the possible permutations of architectures given different weight vectors. Given that we may lack a clear understanding of the intricate relationships among training-free metrics, a linear combination serves as a robust and simple choice that contains sufficient good permutation while being easy to optimize.
Although the concept of a linear combination is straightforward, determining the most suitable weight vector can be challenging. These challenges stem from three main factors. First, there might be insufficient prior knowledge regarding the performance common to inconsistent metric performance across different tasks, shown in Table Second, even there is some prior knowledge, the weight vector in the linear combination plays a rather sophisticated role and does ure shows a scenario where Metrie appears to perform better than Metric 2 in given task (e.g., exhibiting higher Spearman's 's rank correlation). However, to choose Architecture which is the optimum for this task, the weight vector must fall within the dark green region, suggesting that Met- ric generally requires higher weighting than Metrie which is the opposite of their performance when used alone. Third, the optimization process is costly, as it involves querying the objective evaluation metric for the true architecture performance.
metric on a specific task. It's
than merely indicate the importance of metrics. For example, Fig-
4.2 EXPLORATION TO OPTIMIZE THE ROBUST ESTIMATION METRIC
Considering the aforementioned difficulties, employ Bayesian optimization (BO) Snock et al., 2012) to optimize the weight vector. We select BO due to its effectiveness in handling black-box global optimization problems and its efficiency in incurring only small search costs, aligning well with our scenario where the optimization problem is complex and querying is costly. We present algorithm in Algorithm

---

Published as a conference paper at ICLR 2024
Algorithm 1: Optimization of Weight Vector through Bayesian Optimization
1: Input: Objective evaluation metrics J. set of training-free metrics M. the search space A. and the search budget T
2: 2o =
3: for step L... do
4: Update the GP surrogate using 2
5: Choose wy using the acquisition function
6:
Obtain the architecture A(w,)
7: if A(w,) is queried then
8:
Query for the objective evaluation metric / ((A(w))
9:
else
10:
Obtain f(A(ww:) from Q1-1
end if'
12:
Obtain Q - Qt-1 u {(w;, [ ((((w:)))
end for
14: Select the best-queried weight vector vh = arg (a (S(([W)()WWW)))))))))))))))))))) (w, ((A(w)) @r).
Specifically, in every iteration, first set of observations update the Gaussian Process (GP) surrogate, which is used to model the prior and posterior distribution based on the observa- tions (line 4 of Algorithm[I] [T. An observation defined pair of the weight vector and the true architecture performance of the corresponding architecture selected based on the weight vector, as defined in Equation [ Then we choose the next weight vector based on the acquisition function and obtain the corresponding architecture (lines 5-6 of Algorithm D If the true architecture per- formance of this architecture has not been queried yet, we will query from the previous observations (lines 7-11 of Algorithm [T. We update the observation set and when iterations are complete, we select the best-queried weight vector based on the performance of the corresponding architecture (see Appendix B.2 for more implementation details such as the utilized training-fre
Otherwise, we obtain
fanin free metrics). With this weight vector, we answer RQ1 by proposing the robust estimation metric M(: w
4.3 EXPLOITATION TO BRIDGE THE ESTIMATION GAP
As discussed in RQ2, the estimation gap limits the metrics propose superior architecture. This estimation gap also exists in our proposed robust estimation metric.
To bridge this estimation gap, we first need quantify We propose use Precision @ T value, which measures the ratio of relevant architectures within the top 7 architectures based on the esti- mation metrie. Here, an architecture is deemed relevant if it ranks among the top T archiiceite performance architectures. Formally, with an estimation metric M, Precision @T is defined as
(M HA, RM(A) < STAR (A)
T
The reason for adopting Precision @ T value rather than the more conventionally used measurement such as Spearman's 's rank correlation stems from two factors. First, it focuses on the estimation of top-performing architectures rather than the entire search space, which aligns with the goal of finding optimal architecture in NAS. Second, if we employ greedy search on the top T architectures based on the estimation metric M, and propose the architecture
AM. = arg max AEA AEA( (A(),, (M) ST),
then we can directly obtain the expected ranking performance of this architecture, as demonstrated in Theorem I (the proof is given in Appendix A.2 with the discussion about the uniform distribution assumption P (A) = t] 1/T). According to this theorem, a higher Precision T value leads to a better ranking expectation. Hence, using Precision @ T can provide direct analysis of the performance of the proposed architecture.
Theorem 1. Given the estimation metric M and the objective evaluation metric f. define for ATT (A, RM((A) < T A Ry(A) < T). Suppose that v.A E ArT,M.S, VI. E (1,2.... ,7), ((R
5

---

Published as a conference paper at ICLR 2024
Algorithm 2: Robustifying and Boosting Training-Freee Neural Architecture Search (RoBoT)
1: Input: Objective evaluation metrics J. set of training-free metrics M. the search space A. and the search budget T
2: Execute Algorithm I and obtain w", To = (A(ww), (()w),,( (w, f(A(w) ))) @TH
3: Obtain robust estimation metric MM: w and corresponding ranking (-:
4: Propose architecture AKrT = arg max AEA (AA) AM(..)),TTT V E 2r)
t = 1/T. If f) 0, then
T +1 (AR,)) pr(M, fJT +1
Therefore, employ the greedy search (i.e., exploitation) on the robust estimation metric to bridge the estimation gap. Notably, within Algorithm we may not utilize the entire T search budget (as indicated in lines 9-1 Suppose that there are To distinct architectures in Qr (corresponding the number of executions of line 8), this leaves a remaining search budget T To for exploitation. In practice, the magnitude of T To is usually significant compared with T. shown by our experiments in Section 6 Thus, we apply the greedy search among the top '" - To architectures of the robust estimation metric propose the architecture A MM::")),TTTT
By integrating this strategy with Algorithm D. we formulate our proposed method, referred to as robustifying and boosting training-free neural architecture search (RoBoT), as detailed in Algo- rithm 2 This innovative method explores the weight vector hypothesis space to create robust estimation metric and exploits the robust estimation metric to further boost the performance of the proposed architecture, thereby proposing a robust and competitive architecture that potentially sur- passes those proposed by any single training- -freen metric, a claim will substantiate later.
DISCUSSION AND THEORETICAL ANALYSES
Our proposed algorithm RoBoT successfully tackles the research questions RQ1 and RQ2. Yet, the assessment of our proposed architecture Air. is still open- open-ended as the value of Pr(M(. w") remains uncertain. To address this, we incorporate our algorithm into the partial monitoring frame- work and provide an analytical evaluation. Based on these findings, we draw intriguing insights into the factors influencing the performance of RoBoT.
5.1 EXPECTED PERFORMANCE RoBOT
To evaluate Precision @ T value, we note that our Algorithm I fits within the partial monitoring framework (Bartók et al., 2014). Partial monitoring is a sequential decision-
game where the leamerr selects an action, mcurs reward, and receives an observation. The observation is related to the reward, but there is gap between them. our context, the action is the selected weight vector, the observation is the true architecture performance of selected architecture and the reward is the Precision @ T' between the objective evaluation metric and the robust estimation metric. The goal of partial monitoring game is to minimize the cumulative regret, where in our case it is defined
Reg. Et max. PT (MM(sw)),)) pT(M((;
If the cumulative regret is bounded, the expectation of pr(M(;, 2,",, will also be bounded. To quantify the usefulness of the observation, a condition known as global observability is used. A global observable game is one in which the learner can access actions that allow estimation of reward differences between different actions based on the observation. If this condition is met, a sublinear cumulative regret Reg. I (t2/3) can be achieved (Bartók et al. 2014). In our scenario, determine that if the conditions of Expressiveness of the Hypothesis Space and Predictable Ranking through Performance are satisfied, our setup can be considered globally observable (see Appendix A.3 for elaboration). As stated in Kirschner et al. (2020), the partial monitoring can be

---

Published as a conference paper at ICLR 2024
extended to reproducing kernel Hilbert Spaces (RKHS) which contains kernelized bandits (i.e., BO). If the above-mentioned conditions can be satisfied, and we use an information directed sampling (IDS) strategy
acquisition function in BO, our Algorithm I can achieve bounded regret Reg. S O(12/5). Combine the above brings to our analysis of ElRy(Ai
Theorem 2. Suppose the maximum Precision@ @T can be achieved by weighted linear combination pf(Mae, - max pr( (r(((:;w), then for A&er obtained from Algorithm
T+1
E
(5)
(PT(MM, 1) - TT - To) +1
with probability arbitrarily close to when (f(MMr: f) - T 1/3 > 0. The value of qr is fixed when T is fixed and qr depends only logarithmically on
With this, we have presented a bounded expectation estimation of the ranking performance of our proposed architecture. In the following section, we will delve into the insights and practical implications derived from Theorem
Its proof is given in Appendix A.3
5.2 DISCUSSION AND ANALYSIS ON RoBoT
With the information provided in Theorem 2 we would like to discuss some factors that influence the performance of the proposed architecture Aga
Inftuence of To As described in Section the value of To is determined by the number of distinct architectures queried during Algorithm However, under this setting, it implies the value of To is not predictable before we perform BO, and fixed after we perform BO. To analyze the influence of To. we consider an alternative setting in which we strictly require the BO to run for To rounds (and waste the search budget if there are duplicate queries for the same architecture), then conduct exploitation for To rounds. Under this setting, the denominator in Equation will be updated as (PM f' ęT, To 11/3 To) +
There are two interesting insights we would like to bring attention. First, To S T, for a fixed value of To the updated ranking expectation is always worse than the original. Second, as the left and the right terms of the denominator are both influenced by To. To serves as an explore-exploitation trade-off. While carefully choosing a Ty might bring a better ranking expectation, our analysis and later ablation study (see Appendix C.3) suggests that keeping To to be automatically decided as defined in Algorithm would yield better and more robust performance.
Influence of T Interestingly, we find that if there is more search budget provided, our pro- posed architecture is more likely to outperform the architecture proposed by any single training- free metric even if they are given the same time budget, i.e., it is more likely B[R, (Aiar)) < minmeM (IE (AM,.)) when T increases (see Appendix A.4 for derivation). This suggests that there will be more advantage to use RoBoT compared with original training-fre free metrics when more search budget is provided. This claim can be verified our experiments Section
EXPERIMENTS
6.1 ROBOT ON NAS BENCHMARK
To empirically verify the robust predictive performance of our proposed RoBoT algorithm across various tasks, we conduct comprehensive experiments on three NAS benchmarks comprising 20 tasks: NAS-Bench-20L (Dong & Yangl 2020), TransNAS-Bench-
(Duan et al. 2021) and DARTS search space (Liu et al. 2019). Detailed experimental information can be found in Ap- pendix B Partial results are summarized in Table Table and Table with additional illustrations provided in Figure depict RoBoT's performance for different numbers of searched architectures. Full results can be found in Appendix C
We clarify how report the search costs in Appendix [B.2]
The results suggest that our proposed architecture consistently demonstrates strong performance across various tasks, achieving at least similar performance level as the best training-free metric
7

---

Published as a conference paper at ICLR 2024
C100
Object
Jipaw
Nomiil
Deurt
Tea
100
of
a'Saartee Fazhbectuv
RC RERRFOREE PRAG
AVERAGE BBSTT
Thabu Aweaa T0
RS REREFRICE FFA AVETAGE +BC5T
Avarggo
(a) WAS-Bench-201
(b)
and TransNAS BLEAA--Beec---- 101 -mirro re- garding the number of searched architectures. RoBoT and HNAS reported with the mean and standard error of 10 runs, and 50 runs for RS, REA and REINFORCE.
Figure 2: Comparison of NAS algorithms in
Table 2: Comparison of NAS algorithms in NAS-Bench- 201. The result of RoBoT is reported with the mean + standard deviation of 10 runs and search costs are evaluated on Nvidia 1080Ti.
Test Accuracy (%)
Algorithm
Cost (GPU Sec.)
Method
C10
C100
IN-16
ResNet (He et al. 2016
93.97
70.86
43.63
manual
REA*
93.92:10.30
45.15 7..94
12000
evolution
RS (w/o s
93.70-10.36
1.00
44.57:1.225
12000
random
REINFORCE
93,85=00.37
71.71=1.09
45.24+1.18
12000
RL
BOHB
93.61
1.28
44.42.11.49
12000
BO+bandit
DARTS (2nd) (Liu ct al. 2019
54,30=0.00
15.61=0.00
16.32=0..00
43277
gradient
GDAS (Dong & Yang 2019
93,44=0.066
70.61=0.21
42.23++0.25
8640
gradient
DrNAS Chen al. Th
93.98--0.58
72.31=1.70
44.02+33.24
14887
gradient
Shaply-Nur NAS (Xtao
2022
94.05=10.19
03.15=0.26
46.25=:0.25
14762
gradient
3-DARTS et al.
2022
94.00+0.22
72.91-0.43
46.20+0.38
3280
gradient
NASWOT Mellor al.
2021
92.9610.81
6.298-1.22
44.4412.10
306
training-freee
TE-NAS (Chen et al. 2021aa
93.90.10.47
7.524
42.3810.46
1558
training-frre
NASI (Shu al. 2021
93.55=0010
7..20=0014
44.84=1.41
120
training free training- free
GradSign Zhang & Jaa
2022]
93.31-10.77
1..3
42.42.12.81
HNAS (hhu 2022b
94.0410.21
1..75=1.04
4..91
3010
hybrid
Training-Pree
+ Avg.
91.7111..77
66.48_4.94
35.4611.90
2648
enumeration enumeration
Best
94.36
73.51
46.34
3702
RoBoT
94.36-10.00
73.51=10.00
46.34.0.00
3051
hybrid
Optimal
94.37
73.51
47.31
Reportedd by Dong Yang 2020
for nearly all tasks, while the latter is an oracle algorithm in practice it requires enumerate every training-fie frree metric. Furthermore, RoBoT even outperforms this oracle in several tasks (not- ing that the architecture proposed by the best training-free metric can already attain near-optimal performance), which exemplifies RoBoT's potential to boost the training-free metrics rather than just ensuring robustness. As illustrated in Figure 2 comparing RoBoT's performance with that of the best training-free metrics reveals that although RoBoT may initially perform worse, it sur- passes the best after querying more architectures. This observation aligns with our earlier claim in Section 5.2 regarding the influence of T. Moreover, RoBoT generally uses fewer search costs to achieve a similar performance level, which demonstrates its efficiency. Besides, results on DARTS search space presented in Table 4 verifies that RoBoT works well on larger scale search space and practical application as it searches in a pool of 60,000 architectures (please refer to Appendix C22 for more details). Overall, our findings suggest that RoBoT is an appropriate choice for ensuring the robustness of training-free free metrics while having the potential to boost performance.
6.2 ABLATION STUDIES
To substantiate our theoretical discussion and bring additional insights regarding RoBoT, we con- duct series of ablation studies to examine factors influencing performance. These factors include optimized linear combination weights, Precision @ T, To. ensemble methods, choice of training- free metrics, and choice of observation. The results and discussion are in Appendix C.3 Overall,
8

---

Published as a conference paper at ICLR 2024
Table 3: Comparison of NAS algorithms in TransNAS-Bench-1O0 1erench-101-mcrro (4,096 architectures) and macro (3,256 architectures) regarding validation ranking. All methods search for 100 architectures. The results of RoBoT are reported with the mean + standard deviation of 10 runs.
Space
Algorithm
Scene
Object
Jigsaw
Layout
Segment.
Normal
Autoenco.
REA RS sharing)
26:122
23::28
24::22
28:123
22::28
22=20
18:16
40::35
34::22
57467
42-43
41::40
43=41
49:51
REINFORCE
35.128
37.131
40.137
38.132
34.135
33
34.132
HNAS
96:335
147+0
67:+49
480+5520
4+:0
22+0
1391=00
Micro
Training-Free
Avg.
75:145
441+3822
260+2444
325=318
718=1417
802+1563
1698=125
Best
2
1
22
18
3
14
RoBoT
2+00
1::0
17::5
17:34
4=1
8=8
66:70
REA
23+-24
22+-21
21++16
21 +20
17+-20
23-22
19++17
RS (w/ sharing)
35::32
26:224
33#39
29=29
33::38
26=23
31=26
REINFORCE
49.145
37.31
20.122
27.22
51.143
48 48_.99
32.117
HNAS
55220
566:10
1501:52
4916
16:20
204:10
67410
Macro
T Training-Fre Free
Avg. Best
346+248
291+:275
110+777
53+-25
32+:23
7=4
24+22
5
2
RoBoT
1+:0
6+3
3=1
6
2+2
2=0
5=1
Table 4: Performance comparison among SOTA image classifiers ImageNet DARTS search space. The search costs are evaluated on an Nvidia 1080Ti.
Test Error (%)
Params (M)
Search Cost
Algorithm
(M)
(GPU Days)
Top-1
Top-5
Inception-v
Szegedy et al.
2015
30.1
10.1
6.6
1448
MobileNet Howard et al.
29.4
10.5
4.2
569
NASNet-A Zoph et
2018
26.0
8.4
5.3
564
2000
AmoebaNet-A Real et
2019
25.5
8.0
5.1
555
3150
PNAS (Luu
2018
25.8
8.1
5.1
588
225
MnasNet-92 Tan et al.
2019
25.2
8.0
4.4
388
DARTS (Liu et al. 2019
26.7
8.7
4.7
574
4.0
GDAS (Dong & Yang 2019
26.0
8.5
5.3
581
0.21
ProxylessNAS (Ca ci al. 2019
24.9
7.5
7.1
465
8.3
SDARTS-ADV (Chen & Hssihh
2020
25.2
7.8
5.4
594
1.3
TE-NAS (Chen et al.
2021a
24.5
7.5
5.4
0.17
NASI-ADA Shu al.
202T
25.0
7.8
4.9
559
0.01
HNAS Shu al. 20226)
24.3
7.4
5.1
575
0.5
RoBoT
24.1
7.3
5.0
556
0.6
the ablation studies validate our prior discussions and theorem, providing a more profound compre- hension of how these factors affect the performance of RoBoT.
7 CONCLUSION
This paper introduces a novel NAS algorithm, RoBoT, which (a) ensures the robustness of existing training-free metrics via a weighted linear combination, where the weight vector is explored and optimized using BO, and (b) harnesses the potential of the robust estimation metric to bridge the estimation gap, thus further boosting the expected performance of the proposed neural architecture. Notably, our analyses can be extended to broader applications. For instance, estimation metrics can be expanded to early stopping performance (Falkner et al.) 2018 Zhou et al.) 2020), and neural ar- chitectures can be generalized to broader set of ranking candidates. We anticipate that our analysis will shed light on the inherent ranking performance of NAS algorithms and inspire the community to further explore the ensemble of training- metrics, unlocking their untapped potential.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We have included the necessary details to ensure the reproducibility of our theoretical and empir- ical results. For our theoretical results, we state all our assumptions Section 5.1 and provide detailed proof in Appendix A For our empirical results, the detailed experimental settings have been described in Appendix and Appendix C.2 Our code has been submitted as supplementary material.
ACKNOWLEDGEMENT
This research is supported by the National Research Foundation (NRF), Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) pro- gramme. The Mens, Manus, and Machina (M3S) is an interdisciplinary research group (IRG) of the Singapore MIT Alliance for Research and Technology (SMART) centre.
REFERENCES
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero-cost proxies for lightweight nas. In Proc. ICLR, 2020.
Gábor Bartók, Dean P Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial mon- itoring classification, regret bounds, and algorithms. Mathematics of Operations Research, 39 (4):967-997, 2014.
Sergi Caelles, Kevis-Kokits Kokitsi Maninis, Jordi Pont-Tuset, Laura Leal-TTaie Taixé, Daniel Cremers, and Lue Van Gool. One-shot video object segmentation. Proc. CVPR, pp. 221-230, 2017.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. Proc. ICLR, 2019.
Shengcao Cao, Xiaofang Wang, and Kris M Kitani. Learnable embedding space for efficient neural architecture compression. In Proc. ICLR, 2018.
Sougata Chaudhuri and Ambuj Tewari. Online learning to rank with top-k feedback. The Journal of Machine Learning Research, 18(1)3559933453 2017.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search imagenet in four gpu hours: theoretically inspired perspective. Proc. ICLR, 2021a.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. In Proc. ICML, pp. 1554-1565, 2020.
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. DrNAS: Dirichlet neural architecture search. In Proc. ICLR, 2021b.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proc. ICCV, pp. 1294-1303, 2019.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the CIFAR datasets. arXiv preprint arXiv:1707.088/9 2017.
Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. DARTS- Ro- bustly stepping out of performance collapse without indicators. arXiv preprint arXiv:2009.01027 2020.
Zhongxiang Dai, Haibin Yu, Bryan Kian Hsiang Low, and Patrick Jaillet. Bayesian optimization meets bayesian optimal stopping. In Proc. ICMI., pp. 1496-1506, 2019.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated bayesian optimization via thompson sampling. In Proc. NeurlPS, pp. 9687-9699, 2020.
10

---

Published as a conference paper at ICLR 2024
Zhongxiang Dai, Yao Shu, Bryan Kian Hsiang Low, and Patrick Jaillet. Sample-then-optimizz batch 2022.
neural thompson sampling. In Proc. NewrlPS, pp.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale
hierarchical image database. In Proc. CVPR, pp. 248 255, 2009.
Terrance Devries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint 2008::7700.4455 2017.
Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four GPU hours, In Proc. CVPR, pp. 1761-1770, 2019.
Xuanyi Dong and Yi Yang. NAS-Bench-201: Extending the scope of reproducible neural architec- ture search. In Proc. ICLR, 2020.
Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang, Tong Zhang, and Zhenguo Li. Transnas-bench 101: Improving transferability and generalizability of cross-task neural architec- ture search. In Proc. CVPR, pp. 5251-5260, 2021.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization at scale. Proc. ICML, pp. 1437-1446, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proc. CVPR, pp. 770-778, 2016.
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andrectto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint 1XX4::7704048611 2017.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Proc. CVPR, pp. 2261-2269, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. Proc. ICLR, 2015.
Johannes Kirsehner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Proc. COLT, pp. 2328-2369, 2020.
Arjun Krishnakumar, Colin White, Arber Zela, Renbo Tu, Mahmoud Safari, and Frank Hutter. Nas- bench-suite-zero: Accelerating research on zero cost proxies. Proc. NeurlPS Systems Datasets and Benchmarks Track, 2022.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: Single-shot network pruning based connection sensitivity. In Proc. ICLR, 2019.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In
Proc. UAI, pp. 367-377, 2020.
Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-nas: A zero-shot nas for high-performance image recognition. In Proc. ICML, pp. 347-356, 2021.
Chenxi Liu, Barret Zoph. Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Fei-Fei, Alan L. Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proc. ECCV, pp. 19-35, 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proc. ICLR, 2019.
11

---

Published as a conference paper at ICLR 2024
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. In Proc. NeurlPS, pp. 7827-7838, 2018.
Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. In Proc. ICML, pp. 7588-7599 2021.
Xuefei Ning. Changcheng Tang, Wenshuo Li, Zixuan Zhou, Shuang Liang, Huazhong Yang, and Yu Wang. Evaluating efficient performance estimators of neural architectures. In Proc. NeurlPS, pp. 12265-12277, 2021.
Fernando Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014- UtLpsstps://iituubb. wwwp:ttttt.c..o...oooooeoee.e.ee wttp://wwww........e.///.eaeaaaa
Hieu Pham, Melody Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Proc. ICML, pp. 4095 4104,, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. In Proc. AAAI, pp.
2019.
Yu Shen, Yang Li, Jian Zheng, Wentao Zhang, Peng Yao, Jixiang Li, Sen Yang, Ji Liu, and Bin Cui. Proxybo: Accelerating neural architecture search via bayesian optimization with zero-cost proxies. In Proc. AAAI, pp. 9792-9801, 2023.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In Proc. ICI.R, 2019.
Yao Shu, Shaofeng Cai, Zhongxiang Dai, Beng Chin Ooi, and Bryan Kian Hsiang Low. NASI: Label- and data-agnostic neural architecture search at initialization. In Proc. ICLR, 2021.
Yao Shu, Yizhou Chen, Zhongxiang Dai, and Bryan Kian Hsiang Low. Neural ensemble search via bayesian sampling. In Proc. UAI, pp. 1803-1812, 2022a.
Yao Shu, Zhongxiang Dai, Zhaoxuan Wu, and Bryan Kian Hsiang Low. Unifying and boosting gradient-based training-free neural architecture search. In Proc. NeurlPS, pp. 2022b.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv=1409 1556, 2014.
Jasper Snoek, Hugo Larochelle, and Ryan Adams. Practical Bayesian optimization of machine learning algorithms. In Proc. NeurIPS, pp. 2960-2968, 2012.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, pp. 1015- 1022, 2010.
Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proc. CVPR, pp. 1-9, 2015.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V. Le. MnasNet: Platform-aware neural architecture search for mobile. In Proc. CVPR, pp- 2820-2828, 2019.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Proc. NeurlPS, pp. 6377-6389, 2020.
Jack Turner, Elliot J Crowley, Michael O' Boyle, Amos Storkey, and Gavin Gray. Blockswap: Fisher- guided block substitution for network compression budget. In Proc. ICLR, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention All you Need. In Proc. NeurlPS, 2017.
Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In Proc. ICLR, 2020.
12

---

Published as a conference paper at ICLR 2024
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In Proc. AAAI, pp. 10293-10301, 2021a.
Colin White, Arber Zela, Robin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? In Proc. NeurIPS, pp. 28454-28469, 2021b.
Colin White, Mikhail Khodak, Renbo Tu, Shital Shah, Séhastien Bubeck, and Debadeepta Dey. A deeper look at zero-cost proxies for lightweight nas. In ICLR Blog Track, 2022. Utthttps:
https://ielr-
Ronald J Williams. Simple statistical gradient-followine algorithms for connectionist reinforcement
learning. Reinforcement learning, pp. 5-32, 1992.
Han Xiao, Ziwei Wang, Zheng Zhu, Jie Zhou, and Jiwen Lu. Shapley-nas: discovering operation
contribution for neural architecture search. In Proc. CVPR. pp. 11892-11901, 2022.
Quanming Yao, Xu, Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In Proc. AAAI, pp. 6664-6671, 2020.
Peng Ye, Baopu Li, Yikang Li, Tao Chen, Jiayuan Fan, and Wanli Ouyang. 3-darts: Beta-decay regularization for differentiable architecture search. Proc. CVPR, pp. 10864-10873, 2022.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In Proc. ICLR, 2019.
Amir R Zamir, Alexander Sax, William Shen, Leonidas Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proc. CVPR, pp. 3712-3722, 2018.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakehi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In Proc. ICLR, 2020.
Zhihao Zhang and Zhihao Jia. Gradsign: Model performance inference with theoretical insights. In Proc. ICLR, 2022.
Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi, Xuesen Zhang, and Wanli Ouyang. Econas: Finding proxies for economical neural architecture search. In Proc. CVPR, pp. 11396-11400 1404, 2020.
Zhi-Hua Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint 1rXiv:161..01578, 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In Proc. CVPR, pp. 8697-8710, 2018.
13

---

Published as a conference paper at ICLR 2024
APPENDIX A PROOFS
A.1
PROOF OF PROPOSITION
Given the definition of Pearson correlation Prearson PPearsonX
VarlXX]Var\Y we aim to maximize
C
the Pearson correlation between the linear combination of two estimation metrics Mi, Ma and the objective evaluation metric f over wy and w2. For the weights wi, W2 E R, the Pearson correlation is:
M, + m2,22,5]
PPeasson (1IM1 + f2
VVar[u, + w2 [ar[f]
Cov(wi/Mi /] Cov(uz.M2.
([Var[w, Varlwy 2Cov (w1 M1, MaM1f)
wi Cov /]
V[wfVar[M1] + w Var M2 + 2w uy Cov M2l))
Notice that for Pearson correlation, Va -Preasson (X, Y. So if W2 * 0. Ea E R, wl aw2,
0, PPearson (aX, Y) PPearson (X,Y), and Va <
O, PPeasson (aX,Y) hence max(preanon (wiM1 + w2.2.. = max(Prearson (a + M2, PPeasso (a + M2, f), PPearson (M1,
To find out the maximum value of = (aM + M2, we take the derivative of + 1PPParsoma + M2, f) regarding a and set it to O, both yield
[[oMM Cov(M1, [Cr[[[ M21 Cov[Mo. f Marl[MM
Cov[M2, [I. # CoviM1, [|rr] and Cov[Mi, f.Co + Cov[M2, Mar, then the solution given in equation 6 exists and it is non-zero. Since #Preasoon (aM1 + .2. f) only has one critical point and the value of = (a + -M2 f bounded within [-1, (as value of Pearson correlation is bounded within [-1, 1D. equation must correspond to a global optimum for both + (aMM + M2, As Prearson (a.M + M2, f) - PPearson (- + .M22;; J), equation 6 must be global maximum point for one of PPPearson (aM1 + M2, and the global minimum point for the other.
When the global maximum point exists and its value does not equal either PPearson (M1, or PPearson (M2, f), it implies that the value will be strictly larger than both PPearson (M and PPearson (M2. f), given the definition of global maximum. This concludes the proof.
A.2 PROOF OF THBOREM 1
With the uniform distribution assumption, our Theorem I can be derived directly from the following classical lemma.
Lemma 1. Suppose there are n alternatives with distinct ranking 1,2,... , and m 2 alterna- tives {xr pm are uniformly randomly selected from the alternatives. Suppose R(xx) is the ranking value of D,, then
n n+1
m +1
X] where l: Z ZAASK + 1. It should be noted that the lowest ranking value should be at most n + I as there are m alternatives with distinct rankings. Given that the lowest value ranking is k. the remaining m alternatives can be selected from those alternatives with ranking values higher than k. Thus we have:
Proof. Let's first consider the probability that
x-
P
k]
14

---

Published as a conference paper at ICLR 2024
The expectation of the lowest ranking value can be derived
kP
k]
n-kk
m
m++
k
11
m
1
m n-m+11
71 -
(rearranging)
1 k+
1=1
1=k
(8)
n-m++
(using the hockey-stick identity)
m
k=
mm+1l
(using the hockey-stick identity)
mm
(m+ D)!
m (mn
1a-mm]mm
71 +
m + 1
which concludes the proof.
Proof of Theorem For Pr(M. & O, it can be regarded as taking Ar.MM, where | Pr(M, f)T out of the top architectures f. As R2 (AM,)) min (R,( A Ar.M,))- Combining with the uniform distribution assumption (A) = 4 = 1/T, the result can be directly derived from Lemma I which concludes the proof.
Remark The uniform distribution assumption (A) = t] = 1/T is based on the fact, given that do not have prior knowledge about the distribution of the estimation metric A and the objective evaluation metric f, we assume any permutation of architectures has equal probability to be produced by M and f, i.e., probability of 1/N!, where N is the number of architectures. This is aligned with the expectation computation of uniform randomness as stated in Lemmal)
A.3 PROOF OF THEOREM
Before we present the proof, let us first formally introduce the definition of linear partial monitoring game, global observability, information directed sampling (IDS), and their extension to reproducing kernel Hilbert Spaces (RKHS) (i.e., BO). These concepts are proposed by (Kirschner et al.) 2020). Additionally, we will introduce important theorem that establishes the regret bound for globally observable game. Subsequently, we will demonstrate how our algorithm fits into this framework and derive the upper bound on the expected ranking of A Some proof tricks are inspired from (Chaudhuri & Tewari 2017).
Linear Partial Monitoring Game Let X' C Rd be an action set, and 0 E IR be the unknown parameter to generate the reward. For an action x X, the reward is given as (x, 0), and there corresponding known linear observation operator A. mdxm that produces observation as a = A f + e where is an É-subgaussian noise vector. Suppose the game is played for rounds; in round the learner selects action Zt- The goal of the game is to minimize the cumulative regret Reg.. = Σn (x" - 2,, 8), where x² = arg max (x, 8) represents the optimal action.
m-ddimension
15

---

Published as a conference paper at ICLR 2024
Global Observability A linear partial monitoring game is global observable iff Vr, y E 2 span Ag, 2 E X). Here, span(A2,, & E X) is defined as the span of all the columns the matrices (Ag,2 X).
IDS IDS is a sampling strategy minimize the information ratio when sampling a new action from the proposed distribution Specifically, in the round i, the proposed distribution is defined as pt arg min, [.Il((z]
[.(A(()) where A((x) is the conservative gap estimate such that Ae(x) Z (x* - 0) =z,0 and 4xx) is the information gain.
Partial Monitoring in RKHS Also known as the kernelized setting of partial monitoring, the action set now is defined as No, which not necessarily a subset of IR. For every action J. E Xo. non-linearly depends on the features through positive-definite kernel k: Xg x Xy - IR. Let H be the corresponding RKHS the given kernel k. The unknown parameter is now defined as f H (instead of 0), and for the given action x. the reward takes the form of [(z) (Ka, f() The known observation operator is now defined as Ag : H + R"". and thus the observation is a = A + c. The cumulative regret for game played for rounds is Reg, = E f(x*) f(x) (kg- kz, f) where x² = arg max f()). The game is global observable iff Vz, y E No. kz hig e span A2, 2 Xo).
Theorem 3 (Corollary 18 in (Kirschner al., 2020p.. For the kernelized setting of partial monitoring using IDS as a sampling policy, if the game is global observable, then Regn S O(n2/3 + log f)2/33 with probability at least 1 1 where a is the aligument constant where the value is bounded for the global observable game, and Ba, In are variables related to n but only logarithmically depend on n, i.e., Ba, In I O(logn) n).
Next, we would like elaborate on the two conditions we assume to be satisfied.
Expressiveness of the Hypothesis Space For any two weight vectors w1, W2, let M( {AA, RM(ww))(A I T} and (T,M( AT, M. A&T,M( Ew', RM (A) = 1. In simpler terms, this condition necessitates that if the top T architectures of the estimation metrics generated by two weight vectors differ, there must always be a way to evaluate the performance of these architectures through linear combina- tion. Consequently, the hypothesis space produced by the linear combination must be sufficiently expressive. In practice, to enhance the expressiveness of the linear combination, we normalize the values of vriniin-ffree metrics to the range [o, 1]. before performing the linear combination. This normalization increases the likelihood that more architectures can be ranked first by some weight vectors, as no single training-free metric dominates the estimation metric. Our experiments and ablation studies suggest that this condition generally holds for the training-fiee free metries proposed in the literature and the benchmarks commonly employed in the community.
{A,, (M(:sw) (A) I T}. Then VA
Predictable Ranking through Performance For V.A. suppose f(A) is known, then aR,, 1( < T) (A) < T) + where e is an {-subgaussian noise. This assumption requires that we can approximately determine if an architecture is top T in f given its performance, which means the ranking is predictable by the performance. Notice that this ranking threshold es- timator does not need to be explicitly specified, but is used to ensure that for our Algorithm [I] observing f (AA) is approximately equivalent to observing 1( < T) with search budget T. In practice, the benchmark widely used in the community generally satisfies such predictable require- ments.
To begin with our proof for Theorem 2 we first need to prove the global observability of the game to evaluate the expectation of pr (M((;;"),,))
Theorem 4. If the conditions of Expressiveness of the Hypothesis Space and Predictable Ranking through Performance can be satisfied, then
Bipr(M(;; "0 (MMM))) I-1
with probability arbitrary close to where pf (Ma f) is defined in Theorem 2 qr = Ca. 1/3
where oz, Br, PT specified in Theorem 3 and C > O is universal constant.
16

---

Published as a conference paper at ICLR 2024
Proof. To fit our algorithm into the framework of the kernelized setting of partial monitoring, set the action as the weight vector w and the corresponding reward as Pr(M(-: w). f). To derive the closed-form of the kernel ku- the observation operator Aw and the unknown parameter 0 (to prevent ambiguity with the objective evaluation metric f, we still denote the unknown parameter generating the reward (Riws 0) 0), we propose configure Riw, Aw and f as N-dimension vectors where N is the number of the architectures, and (kw); = ((RM(sw) (A.)) S T), (Aw) = ([) (A.) =
1)T, (0); = 1 (R) - T//T.
Intuitively, ( denotes whether A, is within the top T architectures under M(: w), (Aw); indi- cates whether A, is the top architecture under M(: wn), and (0); reveals whether A; is among top T architectures under f. Therefore, the observation is given to ((H)(((()) < 7) + e, indicating whether A(w) is top 'I' architecture under f. Here, A(w) represents the top architecture under M(: w), as per the earlier notation. With a ranking threshold predictor Ry as discussed in Predicatable Ranking through Performance and the performance of f(A(w)), we can provide such observation with Şssubgaussian noise The reward is computed as (kw,0) f). which corresponds to (M w). Notice that for any given weight vector w, the val- ues of liw and Aw are always known the learner (i.e., the learner always which architecture(s) are the top T/oop architecture(s) under (M; w)), thereby fitting our algorithm within the kernelized setting of partial monitoring.
au AT + e, where ow equals
When the condition of Expressiveness of the Hypothesis Space is satisfied, the condition can be directly used derive the global observability, Kmo kiz literally refers the set difference Ar, (M
A (--waa)
With the Theorem we can obtain
Elpr(M(;:'",, M f) RegT T
1
(Ma 1) T
pi(Maa; 9T- 1/33
which concludes the proof.
Proof of Theorem 2 As we have obtained the lower bound of (Elr(( w and as we
search for T To architectures for exploitation to obtain Abar stated in Section 4.3 Theorem can be directly derived from Theorem [ and Lemma which concludes the proof.
A.4 DERIVATION FOR THE CLAIM ABOUT THE INFLUENCE OF IN SECTION 5.2
Suppose that (i max f)), then ((R, S min (B) implies 2. 9TT /Pt 1/(1 - a)). where a = To/T and e pi(Ma, S) (M, The right-hand side can be regarded as the threshold define how good (f should be so that the outperforming can be achieved, and this threshold decreases when T increases, which supports our initial claim.
APPENDIX B EXPERIMENTAL DETAILS
B.1 BENCHMARK INFORMATION
NAS-Bench-201 is widely used NAS benchmark that has served as the testing ground for various training-based NAS algorithms (Pham al.] 2018 Liu et al. 2019 Dong & Yang. 2019) as well as training-free NAS metrics (Abdelfattah et al., 2020 Mellor et al. 2021). The main focus of its search space is the structure of a cell in a neural architecture. In this context, a cell is composed of 4 nodes interconnected by 6 edges. Each edge can be associated with one of five operations: 3 convolution, 1 x convolution, 3 x average pooling, zeroize, or skip connection. Consequently, the search space consists of 56 15,625 unique neural architectures. These architectures are evaluated across three datasets: CIFAR- 10 (C10) (Krizhevsky et al. 2009), CIFAR-100 (C100), and ImageNet-16-122 16-120 (IN-16) @Chrabaszez et al. 2017).
MAS-Bench-200 Dong & Yang, 2020
17

---

Published as a conference paper at ICLR 2024
Ba-nssAAS-Ben (Duan et al., 2021) benchmarks and has been less explored by NAS algorithms. Unlike MAS-Bench-201. which focuses solely on the cell structure, MtansNAA-Benchh-10 explores both micro-cell structure and macro skeleton structure, leading to two distinct search spaces: micro and macro. The micro search space resembles NAS-Bench-200 's structure but features only four operations (omitting the average pool- ing operation), resulting in a total of 4 = 4,096 neural architectures. In the macro search space, the cell structure is fixed while the skeleton is varied. The skeleton contains 4 to modules, each with two residual blocks. Each module can opt to downsample the feature map, double the channels, or times, and channel doubling do both. Across the entire skeleton, downsampling can occur TransNAS-Benchh can happen I to 3 times, yielding a total of 3,256 architectures. these architectures on seven different vision tasks, all using a single dataset of 120K indoor scene images, derived from the Taskonomy project (Zamir et al., (018). The tasks include scene classi- fication (Scene), object detection (Object), jigsaw puzzle (Jigsaw), room layout (Layout), semantic segmentation (Segment.), surface normal (Normal), and autoencoding (Autoenco.).
TransNAS-Bench-ID0 is recent addition to the NAS
evaluates
DARTS (Liu et al., 2019) This search space searches on two cells, where each cell has 2 input nodes and 4 intermediate nodes with predecessors each. On each edge between two nodes, it can have 7 non-zero operation choices. DARTS search space is not tabular benchmark, as it contains total of 10 unique architectures. It evaluates architectures in 3 datasets: CIFAR-1O (C10), CIFAR- 100 (C100), and ImageNet (Deng et al. 2009) datasets.
B.2 IMPLEMENTATION DETAILS OF RoBoT
Algorithm I Details In Section we briefly discussed the use of Bayesian optinization(BO) in our algorithm. We would now delve into the implementation of the Gaussian Process (GP) to con- struct the prior and posterior distributions and the choice of our acquisition function for determining the next queried weight vector. Given a set of observations [](A(w)))),. that they randomly drawn from a prior probability distribution, in this case, GP. The GP is de- fined by mean function covariance (or kernel) function. We set the mcan function to be constant, such as O, and choose the Matérn kernel for the kernel function. Based on these observations and the prior mean and kernel functions, we calculate the posterior mean and kernel function as (w)) and kww, w²) respectively, following Equation (1) in (Srinivas et al., 2010). We then derive the variance as 0² (w) k w. w). As for the acquisition function, we adopt the upper confidence bound (UCB) (Srinivas et al. 2010), as suggested by Kirschner et al. (2020) for its deterministic IDS properties. The next weight vector is chosen as W arg max (lww) kar (w), where is the exploration- exploitation trade-off constant that regulates the balance between exploring the weight vector space and exploiting the current regression results.
[(((w,) ))] we assume
Owing to the capabilitics of BO in solving black-box problems through global optimization, cou- pled with its efficiency, it has enjoyed prolonged period of application within the field of NAS (Cao)
et al. 2018 White et al., [2021]] Ia Shu et al., (022b) [Shen et al. 2023). Although there is a substantial
body of theoretical research in the field of BO (Srinivas et al.) 2010 Dai et al., 2019: 2020 2022). and considerable exploration of theoretical studies within the realm of NAS (Ning et al. 202 Shu
al. 2019 2022b). to the best of our knowledge, this work represents the first instance of applying theoretical findings from the domain of BO to the field of NAS, thereby proposing bounded ex- pected performance with theoretical backing. For more comprehensive understanding of BO, we refer to (Srinivas et al. 2010), and for implementation details, we refer to (Nogueira 2014 both of which guided our experimental setup.
Implementation Details of RoBoT on NAS-Bench-201 and TransNAS-Bench-Ie For both NAS-Bench-200 and TransNAS- Bench-101, we utilize the six training-free metrics outlined in (Ab- delfattah et al. 2020): grad norm, snip, grasp. fisher, synflow, and jacob cov. We pre-calculate these metrics" values for all neural architectures across all tasks. To ensure reproducibility. we directly utilize the computed training-free metrics from Zero-Cost-NAS (Abdelfattah et al., 2020) and
(Krishnakumar et al. 2022) for MAS--Bench-201 and TransNAS-Bendee 101, respectively. For a particular task, we normalize a metric's values to fit within the [o, 1] range. We define the search range of w to be any real value between -1 and given the consideration that it's used for a weighted linear combination to rank architectures. The ranking depends on rel- ative weights rather than their absolute magnitudes, hence normalized range covers all real space
18

---

Published as a conference paper at ICLR 2024
equivalently for the purpose of ranking. For formance after 12 training epochs (i.e., "hp=12") from the tabular data in MAS-Bench-201 as the objective evaluation metric f for all three datasets and compute the search cost displayed in Table 2 in the same manner (which is the training cost of 20 architectures). However, we report the full training test accuracy of the proposed architecture after 200 epochs. As for TransNAA-Benchh Bench-101, we note that for tasks Segment., Normal, and Autoenco. on both micro and macro datasets, the training-free metric synflow is inapplicable due tanh activation at the architecture's 's end, so we only use the remaining five training- maining-free metrics. Moreover, given the considerable gap between val- idation and test performances in TransNAS-Bent MALAA--Bec--O00 101, we only report our proposed architecture's validation performance.
we the CIFAR- 10 validation per-
As for the DARTS search space, we refer to Section C.2 for the implementation details.
Reported Search Costs of RoBoT For Table Table and Table 7 the search costs of RoBoT consist of three components: the computation costs of training-free -fren metrics of the entire search space (which we treat as negligible in early discussion), the queries for objective evaluation performance BO, and in greedy search. To reduce the search costs incurred in queries for objective evaluation performance, we follow (Shu et al. 2022b) to apply the validation performance of each candidate architecture that is trained from scratch for only limited number of epochs (c.g., 12 epochs in NAS- Bench-2011 to approximate the true architecture performance, which in fact is quite computationally efficient (e.g., about I 11 GPU-seconds for the model training of each candidate in MAS-Bench-2011 and 0.04 GPU-day for ImageNet in DARTS search space). Of note, such approximation is already reasonably good to help find well well-performing architectures, as supported by our results.
B.3 IMPLEMENTATION DETAILS OF NAS BASELINES
Throughout our experiments, we focus on the following query-based NAS algorithms:
Random Search (RS) As implied by its name, RS randomly assembles a pool of architectures,
evaluates the performance of each, and proposes the highest-performin one. Despite its simplicity,
this method often proves a strong baseline for NAS algorithms (Yu et al. 2019 Li & Talwalkar 2020), matching the performance stated in Lemma
Regularized Evolutionary Algorithm (REA) (Real et al., 2019) Like RS, REA initiates by as- sembling a small pool of architectures and evaluating each one's 's performance. In our experiments, the initial pool size is chosen to be a third of the total search budget, T/3. Then, the top-performing architecture is removed from the pool and applied to mutation to create new architecture. This new architecture is evaluated and added to the pool. In our context, mutation involves altering one operation on an edge within the cell (or for TransNAS-Bencee ceench-101-mase 101-mo, we randomly add or remove a downsample/doubling operation on one module, and ensure the generated architecture is valid). As it typically assumed that good- pood-peforming architecture's neighbor will perform better than randomly chosen architecture, REA is expected to outperform RS.
REINFORCE (Williams) 1992) REINFORCE is reinforcement learning algorithm that utilizes the objective evaluation metric as the reward to update the policy of choosing architectures. We follow the configuration outlined in (Dong Yang 2020) to use Adam (Kingma & Ba] (015) with the learning rate of 0.01 the optimizer to update the policy and use the exponential moving average with the momentum of 0.9 as the reward baseline.
Hybrid Neural Architecture Search (HNAS) (Shu et al., 2022b Shu et al. (2022b) aims to se- lect the architecture with the minimal upper bound on generalization error, where the upper bound for each architecture is specified with the corresponding training- free metric value and two unknown hyperparameters. HNAS employs BO with the observation of the objective evaluation metric per- formance of the chosen architecture to optimize the values of two hyperparameters. As HÑAS requires that the training-free free metric should be gradient-based, we follow their recommendation and use norm as the training-free metric for our experiments.
Average Training-Free Metric Performance (Avg.) We apply greedy search as stated in Sec- tion 4.3 to traverse the top 7 architectures for each training-free metric and select the architecture
19

---

Published as a conference paper at ICLR 2024
Table 5: Comparison of NAS algorithms in NAS-Bench-201 regarding the ranking of test perfor-
mance.All methods query for the validation performance for 20 models.
Test Ranking
Algorithm
C10
C100
IN-16
REA
814+-1175
789+-891
938+-1170
RS (w/o sharing)
1055+-981
901+9000
815+730
REINFORCE
995+1042
89948814
7224:596
HNAS
2121:10
202:1257
183-151
Training-Free
S Avg.
3331
4514
5256:13785
+ Best
3
24
RoBoT
3+0
1::0
24:00
with the highest objective evaluation performance. The reported performance is the average across all these selected architectures for each training-free metric.
Best Training-Free Metric Performance (Best) Avg.. however, in this case, we report the performance of the single best architecture across all those selected for each training-free metric.
The experimental setup identical that of
APPENDIX C MORE EMPIRICAL RESULTS
C.I ADDITIONAL RESULTS NAS BENCHIMARK
In this section, report additional empirical results MAS-Bench-201 and TransNAS- SaansNAA--Bencc--- 101. The results are provided in Table and Figure 3 TO All the figures on the left side demonstrate the objective evaluation performance while the figures the right side demonstrate the correspond- ing ranking. These additional results align well with our initial results and arguments presented in Section 6.1 further validating that RoBoT offers reliable and top-tier performance across various tasks, achieving competitive as the best training-free metric's s performance without prior knowledge about which training-free free metric will perform the best. Particularly, RoBoT exhibits clear superior performance in tasks like micro-Object, micro-Jigsaw, micro-Normal, macro-Objer and macro- Jigsaw, demonstrating its potential to boost training-free metrics beyond their original performance. Compared with HNAS, our proposed RoBoT shows more stable and higher performance. Despite the decent performance of HNAS in a few tasks such as Seggeet,,,,nt... it struggles with incon- sistency issues inherent to single training-fie frre metrics, leading overall worse performance. In contrast, RoBoT consistently delivers robust and competitive performance, further emphasizing its value for NAS. These additional results strengthen initial conclusions, confirming the robustness, consistency, and superior performance of RoBoT across various tasks on both MAS-Bench-201 and MansNAS-Benchhe 101 benchmarks.
C.2 RoBoT IN THE DARTS SEARCH SPACE
To further verify the robustness of our algorithm RoBoT, we also implement RoBoT in the DARTS [Liu al. 2019) search space, aiming to identify figh-performing architectures in the CIFAR- 10/100 and ImageNet (Deng et al. 2009) datasets. We create pool of 60000 architectures and evaluate their training-free metrics (same as NAS-Bench-201 and -rans-NASS-Ban TLAAS-Bench-100 101, we eval- uate six training-free metrics: grad norm, snip, fisher, synflow, and jacob_cov, and normalize each metric's 's values to fit within the [0. 1] range) on the corresponding datasets. With regards to CIFAR- 10/100, RoBoTis is given search budget 7' 25, to query for the performance of the selected architectures with a 10-epoch model training. As for ImageNet, we use a search budget = 10, and the performance of the selected architectures is determined when they are trained for 3 epochs. As per the methodology the DARTS study (Liu et al.] 2019)), we built 20-layer final selected archi- tectures. These architectures have 36 initial channels and auxiliary tower with weight of 0.4 for
20

---

Published as a conference paper at ICLR 2024
C10
10
212
9-
Test Ener (%)
Test Ranking
24
.2
29
10
15
20
5
10
15
20
C100
211
Test (%)
32
Test Ranking
22
30
2a
10
15
20
5
10
15
20
IN-16
2'
62
Test Error (%)
Test Ranking
2
58
29
54
10
15
20
5
10
15
20
Architectures
RS
REINFORCE
REA
HNAS
AVERAGE
BEST
RoBoT
Figure 3: Comparison between RoBoT and other NAS baselines NAS-Bench-201 regarding the number of searched architectures. Note that RoBoT and HNAS are reported with the mean and standard error of 10 independent searches, while RS, REA, and REINFORCE are reported with 50 independent searches.
CIFAR-10 10 and 0.6 for CIFAR-100, located the 133th layer. We test these architectures CIFAR- 10/100 by employing stochastic gradient descent (SGD) over 600 epochs. The learning rate started 0.025 and gradually reduced to 0 for CIFAR-IO,, and from 0.035 0.001 for CIFAR-100, using a cosine schedule. The momentum was set at 0.9 and the weight decay was 3x 10-4 with a batch size of 96. Additionally, linearly increased from 0 to 0.2 for CIFAR- 10 (and from to 0.3 for CIFAR-100) as regularization techniques for CIFAR-10/100. For the ImageNet evaluation, we train 14-layer architecture from scratch over 250 epochs, with batch size of 1024. The learning rate was initially increased to 0.7 over the first epochs and then gradually decreased zero following a cosine schedule. The SGD optimizer was used with momentum of 0.9 and weight decay of xxx1000 10
use Cutout (Devries Taylor 2017) and ScheduledDropPath, which
We present the results Table and Table 4 Notably, despite lacking prior information on the per- formance of these training-free metrics in the DARTS search space, our proposed algorithm, RoBoT, still delivers competitive results when compared with other NAS techniques. It is worth noting the significant discrepancy between the validation performance (i.e., the performance of the architecture when trained for 10 epochs/3 epochs on CIFAR- 1011000 ImageNet, respectively) and the final test performance (when trained for 600 epochs/250 epochs CIFAR-10/100 ImageNet, respectively).
21

---

Published as a conference paper at ICLR 2024
Table 6: Comparison of NAS algorithms in TransNAS-Bench- (eanch-101-mmen 101-micro regarding validation per- formance. The results of RoBoT and HNAS are reported with the mean and the standard deviation of 10 independent searches, while 50 independent searches for REA, RS, and REINFORCE.
Space
Algorithm
Accuracy
Loss (x10
mloU (%)
(SI00"
Soone
Object
Jigsaw
Layout
Sogment.
Normal
Autocnco.
54.6310.18
44.92.10.38
94.1110.21
62.06.10.69
94.5510.03
57.1010.51
56.2310.81
RS (wio sharing)
54,5620.22
44.7620.339
94.63:0.26
622222=0.96
94,53=00.55
56.8320046
$5.55=+0.99
REINFORCE
54.56=0.19
44.69+0.34
94,70=0.23
-62.20=0.88
94.53=0.03
56.96+0.43
55.75+0.86
Micro
HNAS
54.2920.09
44.0820.00
94,56:2.211
-6483=11.99
94,57=00.00
56,8820.00
48.66:20.00
Training-Free
Avg.
54.60=0.33 36
43.98:00.87
94,11=0.54
64,27==1.27
94.03=1.00 1.07
52.2649..3
41.36=17.29
Best
54.87
45,59
94.76
62.12
94.58
$7.05
55,30
RoBoT
54.87=0.00
45.59:0.000
94.82=0.06
61.16==0.86
94.58=0.00
57,4420,34
$5.42+1.05
Optimal
$4.94
45.59
95.37
-00.10
94.61
58.73
$7.72
REA
56.69=0.34
46.7440.33
96.78=0.10 10
59.99=11000
94.80=0005
60:81:0:722
71.38+2.49
RS (wio sharing)
56.5320.28
46.68-10.00
96.74:0.19
66027-1.008
94.7810.04
60.724:0.72
70.05:13.01
REINFORCE
56.43=0.299
46.67=0.29
80=0.14
-00.9-11.00
94.78=0.04
60.48:0094
69.21+22.55
HNAS
55.03=0.00
45.00=0.00
96.28=0016
61.40 =0.11
94,79=0.00
59.27++0.00
57,59++0.00
Macro
Training-Free
Avg.
55.81=1033
45.87=0087
96,44=0.31
-61.10=1.00 1.20
94,78=0.04
61.19+0.30
70.93+22.84
46.87
94.83
73.51
RoBloT
57.35+0.13
46.94-+0.09
96.92-0.02
58.88-0.70
94.85+0.02
61.66+-0.00
73.53++0.06
Optimal
57.41
47.42
97.02
-58.2
94.86
64.35
74.88
Table 7: Performance comparison among tfateoof-theart (SOTA) neural architectures on CIFAR-
10/100. The performance of the final architectures selected by RoBoT is reported with the mean and standard deviation of five independent evaluations. The search costs are evaluated on a single Nvidia 1080Ti.
Algorithm
Test Error (%)
Params (M)
Search Cost
Search Method
(GPU Hours)
C10
C100
C10
C100
DenseNet-BC (Huang et al.
2017
3.46
17.18"
25.6
25.6
manual
NASNeI-A (Zoph
2018
2.65
3.3
48000
RL
AmoebaNet-A (Real
2019
3.34=0.06
18.931
3.2
3.1
75600
evolution SMBO
PNAS (Luu et af. 2018
3.41=0.09
19.53
3,2
3.2
5400
ENAS P Pham el al.
2018
2.89
19.43*
4,6
4.6
12
RL
NAONel Luo el 2018
3.53
3.1
9.6
NAO
DARTS (2nd) iLiu al.
2019
2.76-0.09
17.54t
3.3
3.4
24
gradient
GDAS Dong & Yang 2019
2.93
18.38
3.4
3.4
7.2
gradient
NASP Yao et al. 2020
2.83=0.09
3.3
2.4
gradient
P-DARTS (Chen et all 2019
2.50
3.4
7.2
gradient
DARTS- (avg) (Chu et al.
2020
2.59=0.08
17.51
3.5
9.6
gradient
SDARTS-ADV (Chen Hsten
2020
2.61=0.02
3.3
31.2
gradient
R-DARTS (L2) Zela
2020
2.95-0.21
18.01
38.4
gradient
DrNAS (Chen et 2021b
2.46=0.03
4.1
14.4
gradient
TE-NAS Chen al.
2021a
2.83-0.66
17.42.10.56
3.8
1.2
training free
NASI-ADA Shu et 202T
2.90-0.13
16.84=1.40
3.7
3.8
0.24
training-fiee free
IINAS (Shu 2022b
2.62-00.44
16.29
3.4
3.8
2.6
hybrid
RoBoT
2.60-0.03
16.52+0.10
3.5
hybrid
While our algorithm RoBoT is not explicitly designed to address this gap, still demonstrates its effectiveness by identifying high-performing architectures. Overall, these results further substanti- ate our previous assertions about the robustness of our algorithm RoBoT in Section 6 suggesting that our approach can be effectively applied in practical, real-world scenarios.
C.3 MORE ABLATION STUDIES
To delve deeper into the factors impacting RoBoT and to provide interesting insights, we carry out several ablation studies detailed below. These studies focus the tasks of Scene, Object, Jigsaw, Segement., Normal on TransNAS-Bendee 101 -0l-ro. The ablation studies explore various aspects of the algorithm and provide valuable findings specific to these tasks.
22

---

Published as a conference paper at ICLR 2024
Ablation Study Optimized Linear Combination Weights To understand the influence of the optimized linear combination weights w" that used to formulate M i²), we present the varying weights the tasks of Scene, Object, Jigsaw, Layout in MaaasNAS--Bench--- 100--001-miiis their similarity and correlation Table and Figure The results show that the optimized weights typically vary for different tasks, which aligns with the observations and motivations in our Section and further highlights the necessity of developing robust metrics that can perform consistently well on diverse tasks such as our RoBo'.. addition, for tasks with similar characteristics, e-g., the Scene and Object tasks, both of which are classification tasks, the optimized weights share relatively high similarit/ccrrreationn, indicating the potential transferability of the optimized linear combination within similar tasks.
well as
Table 8: The varying optimized linear combination weights on 4 tasks of SaatsNAS--Bechhhhh 101- micro.
Tasks
grad norm
snip
grasp
fisher
synflow
jacob .ov
Scene
-1.00
-0.08
-0.97
1.00
1.00
1.00
Object
0.03
-..1
0.76
0.51
0.95
0.16
Jigsaw
-0.74
0.18
0.04
-1.00
-1.00
1.00
Layout
-0.65
-0.27
0.57
-0.48
1.00
0.67
Coole Conlerty
Braven
4:21
Figure 4: Similarity and correlation among the varying optimized linear combination weights on 4 tasks of Mew.A---eenc--1--ieee
Ablation Study on Precision @ T To substantiate claims that the weighted linear combina- tion has better estimation ability and Algorithm can approximate such optimal weight, we demon- strate the Precision @ 100 for the average value of training-free metrics (i.e., E[p f))), the best value of training-free metrics (i.e., (nx (M,,)) the optimal value achievable through linear combination (i.e., (M f)), and the average value of our robust estimation metric (i.e., (lpr([M(: ")), f))). summarized in Table The findings indicate that: (a) the linear combina- tion can augment the Precision @ 100, surpassing that of any individual training-free metric, and (b) the expected Precision @ 100 value of the robust estimation metric exceeds any single training- free metric and close to the optimal possible value, indicating that the robust estimation metric has more potential to be exploited.
Table 9: Values of Precision @ 100 of different estimation metrics MainsNAA-BBech-101-mmee
Precision @ 100
Estimation Metrics
Scene
Object
Jigsaw
Segment
Normal
Average
0.03 + 0.03
0.01 + 0.02
0.01 + 0.01
0.06 + 0.05
0.03 + 0.01
Best
0.08
0.05
0.01
0.14
0.04
Optimal
0.18
0.12
0.06
0.17
0.11
RoBoT
0.14 + 0.02
0.09 + 0.01
0.04 - 0.01
0.15 0.02
0.09 = 0.03
23

---

Published as a conference paper at ICLR 2024
Ablation Study on To As outlined in Section 5.2 examine the impact of To, we can experiment with a setting where we strictly prescribe the value of To. Specifically, with a search budget 7 = 100, we select To from [30, 50, 75, 100]. For this setup, only execute Algorithm[[foor To rounds, and we adjust lines 7-10 in Algorithm| D so now we will always query the architecture that has not yet been queried and holds the lowest ranking value in M(;w,,) After running BO for To rounds, we will apply the greedy search for the top T' - To architectures in M(=ū"", as specified in Section
Figure S demonstrates the outcomes of this experiment. The results highlight that when the BO process concludes (i.e., the exploration phase terminates), there's an immediately noticeable im- provement compared to extending the search in BO as the greedy search commences (i.e., the ex- ploitation phase kicks off). However, if the estimation metric used by the greedy search does not exhibit enough potential (i.e., the Precision @ 100 value is lower), it may be overtaken by those with greater To values. For instance, in the Scene task, while To = 50 outperforms other search budgets initially, it's eventually eclipsed by To 75 when querying for 100 architectures. Allocating all the budget for exploration (i.e., TV = 7' could potentially yield poorer results, as seen in the Scene task. Our original method, RoBoT, typically delivers the best performance, which suggests that reserving the search budget for duplicate queries and applying them in the exploitation phase is a strategic move to enhance performance. Moreover, it boasts the advantage of not having explicitly stipulate the value of To as hyperparameter-ineee
this value is determined by BO itself.
Scone
Object
Jigsaw
Segment
Normal
Validation Pamving
211
21z
212
25.
27
50
100
0
50
100
0
50
100
0
50
100
0
50
100
Number Searched Architecturess
50
ReBoT
Figure 5: Comparison between different values of To and RoBoT on 5 tasks in TransNAS- -Bnnch- 101-micro regarding the number of scarched architectures. Note that all methods are reported with the mean and standard error of 10 independent searches.
Ablation Study on Ensemble Method In this ablation study, we investigate the influence of dif- ferent ensemble methods on the performance of RoBo'.. The original ensemble method in RoBoTT involves a weighted linear combination of normalized training-free metrics, where all these metrics collectively form the hypothesis space. To analyze the impact of this ensemble method, we ex- plore alternative approaches through the following ablation studies: (a) Without Normalization (w/o Normal.): In this approach, we directly employ weighted linear combination of the original val- ues of the training-free metrics to generate estimation metries. (b) Uniform Distribution ( (Uniform Di The values of the training- -fee metries transformed into corresponding ranking values. To maintain the ranking order of architectures, the highest-scoring architecture is assigned a rank- ing value of N 1 instead of 1 for this method, where N is the number of architectures. These transferred ranking values are then used in the weighted linear combination. As the ranking values are uniformly distributed, we refer to this method as Uniform Distribution. (c) Normal Distribution (Normal Dist.): Instead of directly transferring to ranking values, we generate random normal distribution of N values with a mean of 0 and a standard deviation of 1. These values are then sorted and assigned to the corresponding architectures based on their rankings. It's important to note that the ranking of architectures remains unchanged for all the transferred training-fre -fee metrics from the same training- free metric. Thus, all the transferred training-free metrics (from the same training- free metric) have the same Spearman's 's rank correlation and Kendall rank correlation with the objective evaluation metric.
The results, as shown in Figure 66] indicate several key observations. Firstly, compared to using the original values without normalization, the proposed RoBoT demonstrates faster convergence in finding the optimal weight vector, resulting in a smaller value of qr in Theorem 2 This can be attributed to the fact that different training-free metrics often have significantly different magni- tudes, and normalization accelerates the optimization process within the BO framework. Secondly, when compared the Uniform Distribution and Normal Distribution methods that only consider
24

---

Published as a conference paper at ICLR 2024
the rankings instead of the original absolute values of the training-frre free metrics, RoBoT consistently outperforms them. This observation is interesting since the NAS community often relies on Spear- man's 's rank correlation and Kendall's 's rank correlation to assess the quality of a training-fre free metric. However, in this study, we find that all transferred training-free metrics have the same correlation with the objective evaluation metric, yet yield significantly different performances. This suggests that while the absolute values may not be crucial when using single training-free metric in NAS, they play vital role in combining multiple training-free metrics. This finding suggests the existence of untapped potential in leveraging the absolute values for training-free ffree metric combinations, and we encourage further investigation by the research community. Overall, the proposed ensemble method RoBoT, which involves a weighted linear combination of normalized training-free metrics, consis- tently achieves the best performance among the alternative approaches considered in the ablation study.
Scene
Object
Jigsaw
Segment.
Normal
212
Valicareen Hamiing
2'
2
28.
--
00
100
50
100
50
100
50
100
0
50
100
Number of Searched Anchitectures
wib Normal
Unnform Dast
Normal Deet
Hollo!
Figure 6: Comparison between different ensemble methods and RoBoT on 5 tasks in TransNAS- Bench-100 10i--oromm -micro regarding the number of searched architectures. Note that all methods are reported with the mean and standard error of 10 independent searches.
Ablation Study on Utilized Training-Free Metries In this ablation study, we examine the impact of the training-frees ffree metrics used in the linear combination. We consider two scenarios: (a) More training-fft frree metrics, where we include params and flops as additional metrics. This results in a total of 8 training-free metrics for tasks Scene, Object, and Jigsaw, and 7 metrics for tasks Segment. and Normal. Please note that synflow is not applicable for the latter two tasks, as explained in Appendix B.2 (b) Less training-free metrics, where we only utilize grad norm, snip, and grasp for estimation purposes.
The results depicted in Figure demonstrate interesting findings. When utilizing more training-free metrics, the convergence to the optimal weight vector may take longer (as observed in tasks Scene and Object), but has the potential to achieve superior performance (as observed in tasks Jigsaw, Segment., and Normal). The longer convergence time can be attributed to the richer hypothesis space resulting from the inclusion of more training-free metrics. Moreover, the ability to achieve a higher optimum Precision @ T value (fMM, f') is also increased. On the other hand, using fewer training-fres metrics generally leads to poorer performance, suggesting that the selected training- free metrics may not perform well in the given task. In practical scenarios where prior knowledge about training- -free free metric performance is limited, it recommended to include a broader range of training-free metrics for combination.
Scene
Object
Jigsaw
Segmant.
Normal
212
vasidation Pamiing
2
2
24.
50
100
50
100
50
100
50
100
50
100
Number Swarthed Archilectumss
Loss RoBoT
Figure 7: Comparison between utilizing more or less training free metries on tasks in TransNAS- Bench- 1aah-100-miintt regarding the number of searched architectures. Note that all methods are reported with the mean and standard error of 10 independent searches.
A Ablation Study on Observation in Algorithm [ In Section 5.1 we discussed the utilization of the performance of the highest-scoring architecture A( ((w)) the observation in Algorithm 1 and
25

---

Published as a conference paper at ICLR 2024
emphasized its role as partial monitoring of Precision @ T. This raises the question of whether directly observing Precision @ would yield superior results. To explore this, we conduct this ablation study.
The findings, presented in Figure clearly indicate that directly observing Precision ' outper- forms the RoBoT approach. This supports claim about the partial monitoring nature of using the highest-scoring architecture's performance. However, it's important to note that this ablation study purely hypothetical since practical implementation requires having the performance of all archi- tectures beforehand to compute the Precision @ 7 value. Nonetheless, this study provides valuable insights into the observation mechanism employed Algorithm [ and highlights the practicality and effectiveness of using the performance of the highest-scoring architecture as partial monitoring of Precision @ T.
Scene
Object
Jigeaw
Segment
Normal
x
2"
&
25
50
50
50
100
Searched
Figure 8: Comparison between directly using Precision @ 100 as observation and RoBoT on tasks in TransNAS-Bench- 100 101-hirr0 regarding the number of searched architectures. Note that all methods are reported with the mean and standard error of 10 independent searches.
26

---

Published as a conference paper at ICLR 2024
Scene
85.0
Vertaton Reooney
oan on Rarsinn
64.0
04.6
84.0
40
100
30
90
Object
4.55
Vassaton Rankrg
46.0
ng
44.0
100
Jigeaw
95.0
vaktottonn Parnkin
$4.8
34.6
Veidakon
84.0
88.8
20
40
80
100
20
80
100
Layout
-0.60
-0.11
on thencng
10.33
10.64
-0.69
Segment.
04.5
vaacetin Rararng
64.6
64.3
042
04.0
20
40
80
100
883
541
100
0.00
0.67
Uaibbtoon 5004
Wasttiion Purking Paankrg
0.65
0.50
0.52
40
100
30
80
Auloenco.
0.250
0.525
0.450
0.425
40
100
Archicotures
X: BS RERIFORCE REA HRUAS
AVERAGE BEST
ReBul
Figure 9: Comparison between RoBoT and other NAS baselines in TransNAS- -e--S--BBch-1O0 101--001mmmmi regarding the number searched architectures. Note that RoBoT and HNAS are reported with the mean and standard error of 10 independent searches while RS, REA, and REINFORCE are reported with 50 independent searches.
27

---

Published as a conference paper at ICLR 2024
Soene
$7.0
on Parting
28.5
26.0
25.5
40
100
30
50
100
Object
47.0
46.5
46.0
100
Jigeaw
valtartoon Fatartnnaarnng Parking
90.00
66.25-
Valdaion
05.75
06.80
20
40
80
100
20
80
100
Layout
-0.58
-0.59
Wesso on staninn
Vakcadon
10.81
-0.62
-0.64
Segment.
94.25
64.80
64.75
94.00
20
40
100
20
883
50
100
0.62
Uelbbtoon 200M
0.61
0.58
40
50
Auloenco.
Valoaten 0038
0.65
0.60
0.55
40
100
Archicotures
BB RERIFORCE REA
PRUAS
AVERAGE BEST
ReBul
Figure 10: Comparison between RoBoT and other NAS baselines in MlanNNAS-Benchh Mench-101-maa 101-macro regarding the number searched architectures. Note that RoBoT and HNAS are reported with the mean and standard error of 10 independent searches, while RS, REA and REINFORCE are reported with 50 independent searches.
28


Reviews:
[{"review_id": "lMPnIwQ3A9", "reviewer": "Reviewer_3buk", "summary": "This work introduces RoBoT, an algorithm for robustifying and boosting training-free neural architecture search (NAS). Motivated by the inconsistent performance estimation of existing training-free NAS metrics, this work proposes to explore a linear combination of multiple metrics that is more robust than each single metric, and exploit the robustified metric combination with more search budgets. The overall framework includes two stages. The first exploration stage employs Bayesian optimization (BO) to find the best linear combination weights for the robust metric. Then, in the second exploitation stage, the remaining search budgets are used to investigate the top-scoring architectures given by the robust metric. The proposed algorithm, RoBoT, is supported by both theoretical and empirical results.", "questions": "- In Table 3, why are the results on TransNAS-Bench-101 presented as the validation ranking? It seems to be inconsistent with the accuracy/error in the other two datasets (Tables 2 and 4). Also, the search costs are not listed in Table 3.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work is built on existing training-free NAS methods, and extends them to a robustified ensemble. Therefore, the proposed framework is promising for future extension when better training-free NAS methods are discovered.\n\n- Theoretical analysis is provided to understand the proposed algorithm, RoBoT.\n\n- Extensive and solid experiment results on various datasets and settings are provided to demonstrate the efficacy of RoBoT.", "weaknesses": "- Missing details regarding robust metric: It seems that some important details about the BO-searched robust estimation metric are missing. What are the base training-free metrics considered in the search? What are the optimized linear combination weights for them? Do they significantly differ on different datasets/tasks?\n\n- Recent NAS methods: It is suggested to include some more recent NAS methods into the comparison, e.g., Shapley-NAS [1], $\\beta$-DARTS [2].\n\nDisclaimer: Although I know BO and NAS literature, I’m not familiar with the theoretical background in this work. Therefore, I cannot provide helpful feedback on the theoretical part. I would like to read how other reviewers think about the theoretical results.\n\n[1] Han Xiao, Ziwei Wang, Zheng Zhu, Jie Zhou, Jiwen Lu. Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search. In CVPR, 2022.\n[2] Peng Ye, Baopu Li, Yikang Li, Tao Chen, Jiayuan Fan, Wanli Ouyang. $\\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture Search. In CVPR, 2022.", "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": "", "extra_scores": {}}, {"review_id": "G9CeaD9lOg", "reviewer": "Reviewer_GJPv", "summary": "This paper aims to tackle the research gap, the difference between training-free metrics with the final performance. This paper however, propose a weighted linear combination of traditional training free metrics as a estimator, where the weights are obtained automatically via Baysian optimization. Interestingly, this work use partial monitoring theory to prove their method has theoretical performance guarantee. Experiments are conducted on NASBench201.", "questions": "I found the author regularily let the reader \"see later section\" in their introduction, including Section 3 and section 4. I think this is a not a professional way to write the introduction. We should at least grasp the main idea when reading the intro but instead reading the entire paper.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Propose theory seems interesting", "weaknesses": "This paper does not read like an academic paper, where the introduction did not cover the full story. Their related work is quite short to cover the existing literature. I suggest the authors try to read more papers in this field instead of submitting their paper in a rush. Results on NASBench201 shows an incremental improvement without realistic benchmarking their method's performance.", "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": "", "extra_scores": {}}, {"review_id": "hTq1RPbkNo", "reviewer": "Reviewer_81X4", "summary": "This work proposes to find a linear combination of training-free metrics to boost the performance on NAS tasks. Specifically, the authors first train a GP to capture the relationship between weights of training-free metrics and the objective evaluation metric f and obtain a robust estimation metric $M^*$. Then the authors collect the queries during the training procedure of BO as $Q_T$. Finally, the authors utilize the learned $M^*$ as a performance estimator and adopt the greedy search to obtain the best architecture.", "questions": "Please see the weakness.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tThe motivation, that using a linear combination of existing training-free metrics to obtain a robust estimation metric $M^*$, makes sense.\n\n2.\tExperiments on NAS benchmarks show the effectiveness of the proposed method.", "weaknesses": "1.\tThe authors propose to train a BO to capture the relationship between the weight vector and the objective evaluation metric f. However, the queried architecture should be trained from scratch to obtain the objective evaluation during the BO stage, which seems to require large amounts of search costs since a standard BO procedure usually requires tens of queries.\n\nBTW: What does $R_f(A)$ denote in Eq. 1? Does it represent the objective evaluation of an architecture? Since Alg.1 directly uses $f$ to denote the objective evaluation metric, I suggest the authors utilize the same notation.\n\n2.\tI wonder about the effectiveness of the searched robust estimation metric $M^*$. According to Fig. 2, it seems that the optimal architecture has been found in less than 10 queries during the BO procedure. It shows that there is no need to conduct the greedy search through $M^*$, and BO is enough to get the optimal architecture.\n\n3.\tTable 4 shows that RoBoT only requires 0.6 GPU-day to search, does it only count the search cost of the greedy search procedure? I wonder what is the cost of the BO stage, which I am afraid is much larger.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)