Generalizing Few-Shot NAS with Gradient Matching
Authors: Shoukang Hu
Ruochen Wang
Lanqing HONG
Zhenguo Li
Cho-Jui Hsieh
Jiashi Feng
Venue: ICLR 2022 Poster (2022)

Abstract: Efficient performance estimation of architectures drawn from large search spaces is essential to Neural Architecture Search. One-Shot methods tackle this challenge by training one supernet to approximate the performance of every architecture in the search space via weight-sharing, thereby drastically reducing the search cost. However, due to coupled optimization between child architectures caused by weight-sharing, One-Shot supernet's performance estimation could be inaccurate, leading to degraded search outcomes. To address this issue, Few-Shot NAS reduces the level of weight-sharing by splitting the One-Shot supernet into multiple separated sub-supernets via edge-wise (layer-wise) exhaustive partitioning. Since each partition of the supernet is not equally important, it necessitates the design of a more effective splitting criterion. In this work, we propose a gradient matching score (GM) that leverages gradient information at the shared weight for making informed splitting decisions. Intuitively, gradients from different child models can be used to identify whether they agree on how to update the shared modules, and subsequently to decide if they should share weight. Compared with exhaustive partitioning, the proposed criterion significantly reduces the branching factor per edge. This allows us to split more edges (layers) for a given budget, resulting in substantially improved performance as NAS search spaces usually include dozens of edges (layers). Extensive empirical evaluations of the proposed method on a wide range of search spaces (NASBench-201, DARTS, MobileNet Space), datasets (cifar10, cifar100, ImageNet) and search algorithms (DARTS, SNAS, RSPS, ProxylessNAS, OFA) demonstrate that it significantly outperforms its Few-Shot counterparts while surpassing previous comparable methods in terms of the accuracy of derived architectures. 
Our code is available at https://github.com/skhu101/GM-NAS.

Published as a conference paper at ICLR 2022
GENERALIZING FEW-SHOT NAS WITH GRADIENT MATCHING
Shoukang Hul Ruochen Wang²* Langing Hong'
Zhenguo Li Cho-Jui Hsieh² Jiashi Feng*
'The Chinese University of Hong Kong
University of California, Los Angeles
$ Huawei Noah's Ark Lab khu@see cubk. edu. hi chchsich@cs. acla.edu
*National University of Singapore
ruocwangeucla.er
(honglanqing, Li. SthenguoJehuawei.comm jshfengegmail.com
ABSTRACT
Efficient performance estimation of architectures drawn from large search spaces is essential to Neural Architecture Search. One-Shot methods tackle this chal- lenge by training
supernet to approximate the performance of every archi- tecture in the search space via weight-sharing, thereby drastically reducing the search cost. However, due coupled optimization between child architectures caused by weight-sharing One-Shot supernet's performance estimation could be inaccurate, leading degraded search outcomes. To address this issue, Few-Shot NAS reduces the level of weight-sharing by splitting the One-Shot supernet into multiple separated sub-supernets via edge-wise (layer-wise) exhaustive partition- ing. Since each partition of the supernet is not equally important, it necessitates the design a more effective splitting criterion. this work, we propose a gradient matching score (GM) that leverages gradient information at the shared weight for making informed splitting decisions. Intuitively, gradients from differ- ent child models shared modules, and subsequently to decide if they should share the same weight. Compared with exhaustive partitioning, the proposed criterion significantly re- duces the branching factor per edge. This allows us to split more edges (lay- ers) for given budget, resulting in substantially improved performance as NAS search spaces usually include dozens of edges (layers). Extensive empirical evalu- ations of the proposed method on wide range of search spaces (NASBench- DARTS, MobileNet Space). datasets (cifarl0, 10 cifar 100, ImageNet) and search al- gorithms (DARTS, SNAS, RSPS, ProxylessNAS, OFA) demonstrate that it sig- nificantly outperforms its Few-Shot counterparts while surpassing previous com- parable methods in terms of the accuracy of derived architectures. Our code is available https: gighhbttbbb...og com/ sksullll111
be used to identify whether they agree how update the
INTRODUCTION
In recent years, there has been surge of interest in Neural Architecture Search (NAS) (Stanley & Miikkulainen, 2002; Zoph & Le, 2017; Pham et al., 2018; Real et al., 2019; Liu et al., 2019) for its ability to identify high-performing architectures in series of machine learning tasks. Pioneering works in this field require training and evaluating thousands of architectures from scratch, which consume huge amounts computational resources (Miikkulainen et al., 2019; Zoph & Le, 2017; Zoph et al., 2018). To improve the search efficiency, One-Shot NAS (Pham et al., 2018; Liu et al., 2019; Bender et al., 2018) proposes to train a single weight-sharing supernet (Shot) that encodes every architecture in the search space sub-path, and subsequently uses this supernet to estimate the performance of the underlying architectures efficiently. The supernet is represented as a directed acyclic graph (DAG), where each edge is associated with set of operations. In the One-Shot supernet, child models share weight when their paths in the DAG overlap. This way, One-Shot methods manage to cut the search cost down to training single supernet model while still achieving state-of-the-an art performances.
"Equal Contribution

---

Published as a conference paper at ICLR 2022
edge:
Gradient
0.7
cosine similarity
operation:
0.1
0.2
0.3
supernet
supernet
Min-cut
$
supernet 1 0.7
0.2
0.3
supernet
(a) Pew-Shot NAS (depth: branching factor:
(b) GM-NAS (depth: 2, branching factor: 2)
Figure 1: An illustration of the supernet partitioning schema in Few-Shot NAS v.s. GM-NAS (ours)
Despite the search efficiency, training the weight-sharing supernet also induces coupled optimization among child models. Consequently, the supernet suffers from degenerated search outcomes due to inaccurate performance estimation, especially on top architectures (Bender et al., 2018; Yu et al., 2020b; Pourchot et al., 2020; Zhang et al., 2020b; Zhao et al., 2021b). To reduce the level of weight-sharing, Few-Shot NAS (Zhao al., 2021b) proposes to split the One-Shot supernet into multiple independent sub-supernets via edge-wise exhaustive partitioning. Concretely, it assigns every operation on the selected edges to a separated sub-supernet, with weight- enabled only within each sub-supernet (Figure (a)). This way, architectures containing different operations on the split edge are divided into different sub-supernets, thereby disabling weight-sharing between them. Although the performance of Few-Shot NAS surpasses its One-Shot counterpart, its splitting schema naively assigning each operation on an edge to a separated sub-supernet is not ideal. Some operations might behave similarly to each other and thus can be grouped into the same sub- supernet with little harm. In such cases, dividing them up could be a waste precious search budgets while bringing little benefit to the performance. On the other hand, the gain from dividing dissimilar operations considerably out-weights that dividing similar ones.
The above analysis necessitates the design of effective splitting criterion distinguish between these two cases. Consider two child models that contain the same operations on all but the to-be-split edge of the supernet. Intuitively, they should not one copy of weight if their training dynamics the shared modules are dissimilar. Concretely, when these two networks produce mismatched gra- dients for the shared weight, updating the shared module under them would lead to a zigzag SGD trajectory. As a result, the performance estimation of these networks might not reflect their true strength. This can be further motivated by viewing the supernet training as multi-criteria optimiza- tion (Fliege & Svaiter, 2000; Brown & Smith, 2005), where each criterion governs the optimization of one child model; Only similar update directions from different objectives could reduce the loss of all child networks. Otherwise, the performance of some child networks (objectives) would dete- riorate. Based on these inspirations. we propose to directly use the gradient matching score (GM) the supernet splitting criterion. The splitting decision can be made via graph clustering over the sub-supemetss with graph links weighted by the GM scores (Figure (b)). Utilizing the proposed splitting schema, we generalize the supernet spltiigg of Few-Shot NAS support arbitrary branch- ing factors (number of children at each node of the partition tree). With a much lower branching factor, we could afford to split three times more edges compared with Few-Shot NAS under the same search budget, and achieve superior search performance.
We conduct extensive experiments on multiple search spaces, datasets, and base methods demon- strate the effectivvness of the proposed method, codenamed GM-NAS. Despite its simplicity, GM- NAS consistently outperforms its One-Shot and Few-Shot counterparts. On DARTS Space. we achieve a test eтror of 2.34%, ranked top among SOTA methods. On the MobileNet Space, GM- NAS reaches 19.7% Top-1 test error on ImageNet, surpassing previous comparable methods.
RELATED WORK
One-Shot NAS with Weight-Sharing aims at addressing the high computational cost of early NAS algorithms (Bender et al., 2018; Liu et al.. 2019; Li & Talwalkar, 2020). Concretely, One-Shot NAS builds one single supernet that includes all child models in the search space as sub-paths, and allows the child models to share weight when their paths overlap. Architecture search be conducted by
2

---

Published as a conference paper at ICLR 2022
training the supernet once and using it the performance estimator to derive the best child model from the supernet. As a result, One-Shot NAS reduces the search cost down to training one single model (the supernet).
Despite the search efficiency, Weight-sharing technique adopted by One-Shot NAS also posts a wide range of inductive biases due to coupled optimization, such operation co-adaptation (Bender et al., 2018; Li et al., 2019a), poor generalization ability (Zela et al., 2020; Chen et al., 2021), and distorted ranking correlations especially among top architectures (Zhang al., 2020b; Bender al., 2018; Zhao et al., 2021b). As result, the performance estimation of child models from the supernet could be inaccurate. and thus degrades the search results.
Several lines of methods have been proposed to address the degenerated search performance caused by weight-sharing. Search space pruning methods identify and progressively discard poor- performing regions of the search space, so that other models do not need to share weight with candidates from these regions (Liu al., 2018; Li et al., 2019a; Chen et al., 2021; Li et al., 2020a; Hu et al., 2020b). Distribution learning methods aim at inferring sampling distribution that bi- ases towards top performers (Xie et al., 2019; Chen et al., 2021; Hu et al., 2020a; Dong & Yang. 2019). Recently, there emerges new orthogonal line of work that directly reduces the level of weight-sharing by partitioning the search space into multiple sub-regions, with weight-sharinn abled only among models inside each sub-regions (Zhang al., 2020b; Zhao al., 202 Zhang et al. (2020b) shows on a reduced search space that this treatment improves the ranking correlation among child models. Zhao et al. (2021b) further proposes Few-Shot NAS: edge-wise exhaustive partitioning schema that splits the One-Shot supernet into multiple sub-supernets, and obtains sig- nificantly improved performance over One-Shot baselines. Our work generalizes Few-Shot NAS to arbitrary branching factors by utilizing gradient matching score as the splitting criteria and formu- lating the splitting as a graph clustering problem.
en-
METHOD
3.1 FROM ONE-SHOT NAS TO FEW-SHOT NAS
One-Shot NAS One-Shot NAS represents the search space as a directed acyclic graph (DAG), where each node denotes latent feature map and each edge (e) contains operations o from the set O(e), This way, every child model in the search space can be represented as one path in the DAG (a.k.a. supernet). The search process is conducted by first optimizing the supernet once and subsequently using it as the performance estimator derive the best architectures. One-Shot NAS induces the maximum level of weight-sharing: a child model shares weights with every other model in the search space long as they include the same operation(s) on some edge(s). Although weight- sharing supernet drastically reduces the search cost, it also leads to inaccurate performance estima- tion of child models, as pointed out by several previous works (Zela et al.. 2020; Bender et al., 2018; Zhang et al., 2020b; Zhao et al., 2021b; Wang et al., 2021b).
Few-Shot NAS To address the aforementioned issue in One-Shot NAS, Zhao et al. (2021b) pro- poses Few-Shot NAS that leverages supernet splitting to reduce the level of weight-sharing in One- Shot supernet. Few-Shot NAS divides the One-Shot supernet into multiple sub-supernets (each cor- responding to a "shot"), where weight-sharing occurs only among the child models that belong to the same sub-supemnt.. Concretely, it adopts an edge-wise splitting schema: It first randomly selects target compound edge from the supernet and then assigns each operation a separated sub-supernet, while keeping the remaining edges unchanged. As a result, child models containing different operations fore do not share weight with each other. As shown in Figure I (a), this supernet splitting schema forms partition tree of supernets, with a branching factor B equals to the number of operations on the edge ((O(e)))
the target edge into
the target edge assigned different sub-supernets, and there-
3.2 GENERALIZED SUPERNET SPLITTING WITH ARBITRARY BRANCHING FACTORS
Due to the exhaustive splitting schema, Few-Shot NAS suffers from a high branching factor per split. Suppose we perform splits on T edges, the number of leaf-node suberutssset becomes | On DARTS Space, where the supernet contains operations per edge and 14 edges per cell, splitting
3

---

Published as a conference paper at ICLR 2022
merely two edges lead to 72 = 49 sub- sub-supernets. Consequently, conducting architecture search over these many sub-supernets induces prohibitively large computational overhead. For this reason, Few-Shot NAS could only afford to split very few edges (in fact, one single split in most of its experiments). This could be suboptimal for many popular NAS search spaces as the supernets usually contain multiple edges/layers (14 for DARTS Space and 22 for MobileNet Space), and the decision on a single edge might not contribute much to the performance.
Given a fixed search budget, measured by the total number of leaf-node sub-supernets, there exists a trade-off between the branching factor and the total number of splits. Exhaustive splitting can be viewed as an extreme case with a maximum branching factor. However, naively separating all operations on an edge might be unnecessary: Since some operations might behave similarly, splitting them into separated sub-supernets wastes lot of search budgets while enjoying little benefit. In such a case, we could group these operations into the same sub-supernet with minor sacrifice. This reduces the branching factor, allowing us to split more edges for a predefined budget and improve the search performance on large NAS search spaces with many edges/layers. We term this splitting schema as Generalized Supernet Splitting with arbitrary branching factors.
We provide formal formulation for this proposed splitting schema. At each split, we select an edge e and divide the operations on it into B disjoint partitions: O(+) US.=1-.B O B is thus the branching factor. For Few-Shot NAS, = ( and ( is simply unit set with one operation from edge e. When B < |0(e), more than one operations on the target edge will be assigned to the same sub-supernet, i.e. | > Let & denote the set of all edges and & be the set of partitioned edges after t splits, then any sub-supernet generated after the t-th split can be uniquely determined
by the partitioning set P. {e, of e E E. where Pa contains tuples (e, Ol that record which operations on edge get assigned to this sub-supernet. Let Ap, denote a sub-supernet with partition set Pe, then
Ap, =
U
) o(+)).
(1)
(e,
NEEVE
3.3 SUPERNET SPLITTING VIA GRAPH MIN-CUT WITH GRADIENT MATCHING SCORE
Generalized Supernet Splitting necessitates the design of splitting criterion for grouping op- erations, which leads to a question as to how to decide which networks should or should not share weight. A naive strategy is to perform the random partition, with the underlying assump- tion that the weight-sharing between all child models are equally harmful. However, empiri- cally we find that this treatment merely matches exhaustive splitting in terms of their perfor- mance, and in some cases even worsens the re- sults. To demonstrate this, we compare random partition with the Few-Shot NAS (exhaustive) on NASBench201 (Dong & Yang, 2020) with four operations (skip, conv_IxI. conv_3x3, avg- pool.3x3) For random partitioning, we split two edges on its supernet (T 2), and divide the operations on each edge into two groups randomly (B- = 2). This leads to four sub-supernets, same as Few-Shot NAS with one single split. As shown in Table 1, random split degrades the search performance for both continuous and sampling-bant She-Shot NAS. The comparison result reveals that the weight-sharing between some child models are much more harmful than others, and therefore need to be carefully distinguished.
Table 1: Comparison of different splitting schema on NASBench-201 and CIFAR-10. We run each method with four random seeds and report the mean accuracy of derived architectures. With the same amount of supernets, the search per- formance of random split with smaller branching factor is worse than Few-Shot NAS' exhaustive splitting. However, replacing random split with the proposed Gradient Matching criterion signifi- cantly improves the results (More on this later).
Base
Spilt Criterio
Beanch Factur
Rsplis
Supeewch
Accuracy
Fshnustive
$8.55%
DARTS
Randon
1
70.47%
Gradicre (ours)
2
93.95%
Lshaustive
Random
Gradient
92.52%
If not all weight-sharing are equally harmful, how should we decide whether two models should be split into separated sub-supernets? Intuitively, networks should not share weight if their training dynamics mismatch at the shared modules. In other words, they disagree how to update the
Using 4 operations allow match the number of supernets between random and exhaustive split.
4

---

Published as a conference paper at ICLR 2022
shared weight. In this case, the angles between gradient directions produced by two networks the shared modules might be large, leading to a zigzag pattern of SGD trajectory. As a result, the performance estimation of these models in the supernet could be inaccurate, thereby degrading the performance of downstream architecture search task.
To show this, we evaluate the performance of single model A when updated together with another network Agim that produces similar gradients at shared weight, and compare the performance with the same model updated together with network Adissim that produces dissimilar gradients. We generate (A, Aaim Adissim by sampling from the NASBench-201 search space, in a way that they have the same operation (and thus share weights) on all but one edges (More on this in Appendix B B.2). We then proceed to train (A, Asim) together and similarly (A, Adissim) together via Random Sampling with Parameter Sharing (RSPS) (Li Talwalkar, 2020), and record A's performance un- der these two cases. As shown in Table 2, A achieves a much lower loss when updated together with Asims where gradients from two child models are similar at the shared module. The result indicates that weight-sharing could be more harmful between networks with dissimilar training dynamics.
Inspired by the above analysis, we propose to measure the harmfulness of weight-sharing be- tween child models (hence sub-supernets) di- rectly via gradient matching (GM). Concretely, consider two operations from an edge; if these operations, when enabled separately, lead to drastically different gradients on the shared edges, we give them higher priority for being split into different sub-supernets during the su- pernet partitioning. The entire splitting schema can be formulated as a graph clustering problem: Given a (sub- jub-))supemnt Ap..., we evaluate the gradient of the supernet when each operation is enabled on edge e separately, and then compute the cosine similarity between every pair of these gradients:
Table 2:
Performance of network when updated with a model with similar training dynamics v.s. with model with dissimilar training dynamics at their shared weight. The network achieves a much lower loss in the first case.
Weight Shartigg
Grad Similarity 0.16=0.17
Train Lass
Valid
(4. Anicon))
0.12 0.06
0.82 0.03
0.99 = 0.03
GM (M
ww, Ll COS
V., A(Ap.alo w:)]
(2)
where Ap,-ıle==o means to enable operation on edge of supernet Ap.-,. and W; is the shared weight. This leads to a densely connected graph (Figure 1 (b)) where the vertices are operations on e, and links between them are weighted by GM score computed in Eqn. (2). Therefore, supernet partitioning can be conducted by performing graph clustering on this graph, with the number of clusters equal the desired branching factor. There exist many applicable algorithms for solving this problem, but |O()) is usually small, we perform graph min-cut via brute-force search to divide the operations (supernets) into B balanced groups. For B 2, it can be written as:
u arg min (gaat)
Σ o'
Ap. Ae,=0=)
s.t. [|0() < | < [10()1/2].
where {21 O(e) (2) are the obtained partitions. The proposed splitting schema substantially im- proves the search performance over exhaustive split and random split, as evidenced by Table
3.4 THE COMPLETE ALGORITHM
Edge selection using gradient matching score Apart from smartly selecting which operations should be grouped within an edge, we can also use the gradient matching score to select which edge to split next. More specifically, the graph min-cut algorithm produces cut cost for each edge the sum of gradient matching scores of the cut links on the gradient similarity graph. This can serve as an edge importance measure for determining which edge to split on next, as lower cut cost indicates that splitting on this edge first might relieve the adverse effect of weight-sharing to larger extend. Empirically, we find that this edge scoring measure reduces the variance over random selection used in Few-Shot NAS, and also improves the performance (Section 5.1).
Supernet splitting with restart During the supernet splitting phase, we warmup the supernet' weight (w) for few epochs before each split, in order to collect more accurate gradient information
5

---

Published as a conference paper at ICLR 2022
along the optimization trajectory. Since the effect of weight-sharing has already kicked in during this phase, we re-initialize all the leaf-node sub-supernets after the final split is completed, and conduct arccitecttrr search over them from scratch. The complete algorithm is summarized in Algorithm in the Appendix.
EXPERIMENTS
In this section, conduct extensive empirical evaluations of the proposed method across various base methods (DARTS, RSPS, SNAS, ProxylessNAS, OFA) and search spaces (NASBench-201, DARTS, and MobileNet Space). Experimental results demonstrate that the proposed GM-NAS con- sistently outperforms its Few-Shot and One-Shot counterparts.
4.1 NASBENCH-200
We benchmark the proposed method on the full NASBench-225 201 Space (Dong & Yang, 2020) with five operations (none, skip, conv 1x1, conv 3x3, avgpool 3x3). We run the search phase of each method under four random seeds (0-3) and reports the mean accuracy of their derived architectures, well the standard deviation to capture the variance of the search algorithms. For our method, we split the operations on each edge into two groups (one group with three operations, another group with operations), and one supernet less than Few-Shot NAS, which uses five sub-supernets due to its exhaustive splitting schema.
edges in total, amounting four sub-supernets. Note that this is
Still, the proposed method improves over Few-Shot NAS by large margin. As shown in Table 3, the architectures derived from GM DARTS achieve an average accuracy of 93.72% on CIFAR-10 leading to an improvement of 5.17% over Few-Shot DARTS and 39.24% over DARTS. To further test the generality of the proposed method over various One-Shot NAS algorithms, we also compare GM-NAS with Few-Shot NAS on sampling-bases methods such as SNAS and RSPS. As before, our method consistently out-performs Few-Shot NAS and One-Shot base methods by a substantial margin. Notably, when combined with the proposed method, SNAS matches the previous SOTA result (DrNAS) on CIFAR-10 and CIFAR-100.
Table 3: Comparison with state-of-the-an art NAS methods on NASBench-201.
Method
CIFAR-10
CIFAR-100
SmageNNet16-112
validation
test
validation
Test
ResNet (He 2016)
90.83
93.97
70.42
70.86
44.53
43.63
Random basclinc)
90.93 + 0.36
93.
0.336
70.60 1.37
70.60
1.38
12.92 2.00
12.96 4 2.15
Reinforce (Zoph al., 2018)
91.09 0.37
93.85 + 0.37
70.05
1.67
70.17 +
43.04 2.18
43.16 2.28
ENAS et al, 2018)
39.77
1 0.00
54.30
1 0.000
10.23 1 0.12
10.02
0.27
16.43 0.00
16.32
1 0.00
GDAS (Dong Yang, 2019)
90.01
93.23
8.08
40.66 0.00
0.00
DSNAS (Hu al., 2020s)
89.66 = 0.29
93.08
0.13
30.87 = 16.16
31.01 + 16.38
40.61 + 0.09
11.07 0.09
PC-DARTS (Xu et 2020)
89.96 + 0.15
93.41
0.30
67.12 0.39
67.48
0.89
40.83 0.08
11.31
0.22
DiNAS (Chen el al., 2021)
2021)
91.55 1 0.00
94.36
0.00
73.49 0.00
73.51
0.00
46.37
0.00
46.34 1 0.00
RSP & Talwalkar, 20200
84.16 1.69
87.60
1.08)
45.78 6.33
46.00
6.57
31.00
5.65
30.75 6.12
Few Shot RSPS
85,40 + 1.28
89.11
58.59 3.45
58.69
3.75
34.24 1.45
33.85 2.33
GM RSPS
89.09 0.40
92.70 = 0.53
68 0.991
68.81 :: 1.28
42.65
1.04
43 1: 1.02
DARTS [Liu et al., 201,)
30.77
54.30 0.00
0.00
38.97
0.00
18.87
0.00
18.41 0.00
Few Shot DARTS
84.70 +- 0.44
88.55 4 0.02
70.17 + 2.66
70.16
2.87
31.16
3.93
30.09 + 4.43
DARTS
91.03 = 0.24
93.72 0.12
71.61 0.662
71.83
0.97
42.19 0.00
42
SNAS (Xie et al., 2019)
90.10 1: 1.04
92.77 1 0.53
69.69
2.39
69.34
1 1,98
42.84 1.79
43.16 2.64
Few Shot SNAS
90.47 + 0.48
93.88
0.25
71.28 1.20
71.40
1.41
46. 0.35
46 (6.43 0.19
GM SNAS
91.35 0.00
0.00 91.36
0.000
73.51 0.00
46.37
16.31 0.00
optimal
91.61
94.37
73.49
73.51
46.77
47.31
4.2 DARTS SPACE
We further investigate the performance of the proposed method on the DARTS search space. To encourage fair comparisons with prior arts, we follow the same search and retrain settings as the original DARTS (Liu et al., 2019). Similar to the experiments the search phase of each method under four random seeds (0-3) and report the best and average accuracy of all derived architectures, well the error bar to capture the variance of the search
NASBench-201,
also

---

Published as a conference paper at ICLR 2022
Table 4: Comparison with state-of-the-an NAS methods on CIFAR-10.
Test Error(%)
Param
Search Cost
Search
Architecture
Best
Avg
(M)
(GPU Days)
Method
DenseNet-BC (Huang et al., 2017)
3,46
25.6
manual
NASNet-A (Zoph et al., 2018)
2.65
3.3
2000
RI.
AmocbaNct-A (Real ct al., 2019)
3.34 = 0.06
3.2
3150
evolution
AmoebaNet-B (Real et al., 2019)
2.55
0.05
2.8
3150
evolution
PNAS (Liu al., 2018)
3.41 = 0.00
3.2
SMBO
ENAS (Pham
2018)
2.89
4.6
RI.
NAONet (Luo et al., 2018)
3.53
3.1
0.4
NAO
GDAS (Dong Yang. 2019)
2.93
3,4
0.3
gradient
BayesNAS (Zhou et al., 2019)
2.81 +: 0.04
3.4
0.2
gradient
ProxylessNAS (Cai al., 2019)t
2.08
5.7
4.0
gradient
PARSEC (Casale el al., 2019)
2.81 1. 0.03
3.7
gradient
P-DARTS (Chen ct al., 2019)
2,50
3.4
0.3
gradient
CNAS (Lim et al., 2019)
2.60 0.06
3.7
0.3
gradient
ASNGNAS (Akimoto et al. 2019)
2.54 = 0.05
3.3
0.1
gradient
PC-DARTS el al., 2020)
2.57 0.07
3.6
gradient
SDARTS-ADY (Chen & Hsich, 2020)
2.61 0.02
3.3
1.3
gradient
Me (Wang al., 2020b)
2.68 0.01
2.9
0.6
gradient
ISTA-NAS (two stage) (Yang et al., 2020)
2.54 1 0.05
3.3
0.1
gradient
NASP (Yao ct al., 2020)
2.83 + 0.09
3.3
0.9
gradient
SGAS (Li et ul., 2020s)
2,39
2.66 = U.24
3.7
0.25
gradient
DrNAS (Chen ct al., 2021)
2.54 + 0.03
4.0
gradient
DARTS (Ist) (Liu et al., 2019)
3.00 + 0.14
3.3
gradient
Few Shot DARTS (Ist)
2.48*
2.60
0.10
3.6
gradient
GM + DARTS (1st)
2.35
2.46
0.07
3.7
gradient
DARTS (2nd) (Liu et 2019)
2.76 0.09
3.3
1.0
gradient
Few Shot DARTS (2nd)
2.58
2.63
0.06
3.8
2.8
gradient
GM + DARTS (2nd)
2,40
2.49
0.08
3.7
2.7
gradient
SNAS (moderate) (Xie et al., 2019)
2.85
0.02
2.8
1.5
gradient
Few Shot SNAS
2.62
2.70
0.05
2.9
1.1
gradient
GM + SNAS
2.34
2.55
0.16
3.7
gradient
Reproduced by rumning both search und retrain phase under four seeds. Few-Shot NAS adopts different retrain protocol than the commonly used DARTS protocol; The test accuracy of its released discovered architecture under DARTS' protocol is 2.44%, similar to our reproduced "best" result on DARTS-Ist (2.48%). Obtained on a different search space with PyramidNet (Han al., 2017) as the backbone.
algorithmss 2, For GM-NAS, we select three edges (I' 3) in total based on the edge importance measure introduced in Section 3.4 and split the operations on each selected edge into two groups the seven supernets used in the Few- Shot NAS baseline. We also restrict our total search cost to match that of Few-Shot NAS for fair comparisons. We refer the readers to Appendix C for more details about the settings.
(B 2). This leads eight sub-supernets, comparable
As shown in Table 4, GM-NAS consistently outperforms Few-Shot NAS on both variants of DARTS and also SNAS. For instance, GM DAR'S (Ist) achieves 2.35% test error rate, 0.13% lower than Few-Shot DARTS (Ist). In addition, GM-NAS also achieves significantly better average test accuracy (Avg column) than Few-Shot and One-Shot NAS, which shows the robustness of our search algorithm under different random seeds. Notably, the best test error obtain across different base methods is 2.34% (GM-SNAS), ranking top among prior arts.
4.3 MOBILENET SPACE
In addition to the cell-based search spaces, we also evaluate the effectiveness of GM-NAS on the MobileNet Space. Following Few-Shot NAS, we apply GM-NAS to two sampling-bast based methods ProxylessNAS (Cai et al., 2019) and OFA (Cai et al., 2020). To match the total number of sub- supernets of GM-NAS with Few-Shot NAS, we select two layers (T = 2) to perform the supernet partitioning, and divide the operations into two groups (B = 2) for the first edge, and three groups (B = 3) on the second edge.
The results summarized in Table 5. When applied to ProxylessNAS, GM-NAS achieves Top-1 test error rate of 23.4%, out-performing both Few-Shot and One-Shot versions by 0.7% and 1.5%, re- spectively. On OFA, obtain 19.7% Top-1 test error, surpassing all comparable methods within 600-FLOPs latency. The strong empirical results demonstrate GM-NAS' ability to effectively re-
NNoe that previous methods usually pick the best architecture from up to 10 search runs and report the standard deviation of only the evaluation phase. Such reporting schema does not capture the variance of the search algorithm, and thus biases toward highly unstable methods.
7

---

Published as a conference paper at ICLR 2022
Table 5: Comparison with state-of-the-arr image classifiers on ImageNet under mobile setting.
Test Error %)
Params (M)
Flops
Search Cost
Search
Architecture
top-1
top-5
(M)
(GPU days)
Method
Inception-ll (Szegody al., 2015)
10.1
manual
MobileNet (Howard al., 2017)
29.4
10.5
569
manual
ShuffleNet 2x (v1) (Zhang et ul. 2018)
26.4
10.2
524
manual
ShuffleNet 2x (v2) (Ma et 2018)
25.1
591
manual
NASNef-A (Zoph
2018)
8.4
564
2000
PNAS (Liiu
2018)
25.8
8.1
225
SMBO
AmoebaNet-C (Real (Real al., 2019)
24.3
7.6
6.4
570
3150
evolution
MnasNet-92 (Tan et al. 2019)
25.2
8.0
4.4
388
RL
GDAS (Dong Yang. 2019)
26.0
8.5
5.3
581
gradient
BayesNAS (Zhou
2019)
26.5
8.9
0.2
gradient
PARSEC (Casale al., 2019)
26.0
8.4
5.6
gradient
P-DARTS (CIFAR-10) (Chen 2019)
24.4
7.4
4.9
557
0.3
gradient
SinglePathNAS (Gun of al., 2019)
25.3
3.4
328
evolution
EfficientNee-BB B1 (Tan & Le, 2019)
20,9
5.6
700
grid scarch
DSNAS (Hu et al., 2020aaf
25.7
8.1
gradient
ISTA-NAS (Yang al., 2020)!
24.0
7.1
gradient
PC-DARTS (ImageNet) Net) (Xu
2020)
7.3
gradient
BigNASModeI-L (Yu al., 2020a)
20.5
gradient
GAEA PC-DARTS (Li et al., 2020b)
24.0
7.3
gradient
DrNAS (Chen al., 2021)1
23.7
7.1
5.7
604
4.6
gradient
DARTS (Liu 2019)
26.7
8.7
4.7
574
1.0
gradient
GM-DARTS (2nd)
24.5
7.3
5.1
574
2.7
gradient
SNAS (mild) (Xie et 2019)
9.2
gradient
GM-SNAS
24.6
7.4
583
gradient
ProxylessNAS (GPU) (Cai et., 2019)
24.9
7.5
gradient
Few Shot ProxylessNAS (Zhao al., 2021b)
24.1
521
20.75
(11.7)"
gradient
GM ProxylesNNASt
23.4
7.0
4.9
530
24.9
gradient
OFt_Net (Large) (Cai al., 2020))
20.3
(20.0)-
(5.1)
9.1
595
1.75
gradient
Few Shot OFA_Nc Net (Large) (Zhao et al., 2021b)
20.2 (19.5)F
5.2
9.2
600
1.75
gradient
GM Oet (Large)"
19.7
5.0
9.3
587
1,7
gradient
The architecture discovered ImageNet directly, otherwise it discovered CIFAR-10 (Transfer Setting).
The search cost of Few-Shot ProxylessNAS (20.75) is estimated bused on the code we obtained from the author, which different from the one reported in the original paper (11.7).
"x(y)"" denotes
reproduced results and y the one reported the original pupers. refer reader to Appendix
D.3 for discussions reproducibilitt.
We follow OFA and Few-Shor OFA paper to report the search cost, which only includes the cost of evolutionary search.
duce the harm of weight-sharing in One-Shot Algorithms on large-scale search spaces and datasets, compared with Few-Shot NAS. We also evaluate the performance of transferring the searched archi- tectures (GM-DARTS and GM-SNAS) in CIFAR-10 to the ImageNet task, which further validates the effectiveness of our GM-NAS methods.
ABLATION STUDY
In this section, we conduct extensive ablation studies on GM-NAS. Similar Section 3, we use CIFAR-10 and NASBench-201 space with four operations as it allows us to align the number of supernets with Few-Shot NAS and establish proper comparisons.
5.1 THE EFFECT OF DIFFERENT COMPONENTS IN THE PROPOSED METHOD
Gradient similarity measures We examine the effect of different similarity measures for computing the gradient matching score on the proposed method. We compare cosine simi- larity with la distance, as well as per-filter co- sine similarity (Zhao et al., 2021a) that com- putes cosine similarity for each convolution fil- ters separately. As shown in Table 6, per-filter cosine similarity performs similarly to cosine similarity while distance is not effective. We therefore adopt cosine similarity for its simplicity.
Table 6: Test Accuracy (%) of the derived
chitectures from GM-NAS with different gradient similarity measures NASBench-201. Two vari- ants of Cosine similarity perform similarly while L2 distance is not effective.
Measure Accuracy
L
Per-Filter-OOS
COS
92.52 2 0.93
93.87
93.87
93.96 0.088
Edge selection using gradient matching score Instead of randomly selecting edges to parti- tion the supernet on, GM-NAS leverages the cut cost from graph min-cut to decide which edge partition on. Empirically, find that this technique reduces the variance and also improves
8

---

Published as a conference paper at ICLR 2022
the search performance compared with random selection. GM-NAS with random edge selection obtains 93.58% mean accuracy with a standard derivation of 0.39 on NASBench-201. In contrast, GM-NAS with the proposed edge selection achieves 93.95% accuracy with only faction of the variance (0.08).
Warmup epochs during the Splitting phase
To obtain accurate gradient information, we warmup the supernet for few epochs during
95.0
Test Accuracy (%)
the supernet partitioning phase. As shown in Figure 2, our proposed method robust to
94.5
94.0
wide range of warmup epochs. Note that the variance increases without warmup (warmup epoch = 0) due to noisy gradients at initializa- tion, indicating that proper supernet warmups are necessary for GM-NAS.
93.5
93.0
92.5
5
15
20
Warmup Epochs
Restart After the final split completed, we re-initialize the weights of sub-supernets be- fore conducting architecture search on them. Intuitively, restarting the sub-supernets elimi- nate the negative effect weight-sharing estab- lished during the splitting phase. To verify this, we test GM-NAS without restart while keeping the number of supernet training epochs identical to the GM-NAS baseline. We obtain mean accu- racy of 91 ..04% on CIFAR-10, which is 2.91% 99% lower than the original GM-NAS, which shows the necessity of supernet restart.
Figure 2: Test Accuracy (%) of the derived chitectures from GM-NAS with different super- warmup epochs during the supernet splitting phase on NASBench-201. The performance of GM-NAS stays stable across different settings.
5.2 RANKING CORRELATION
We also evaluate the ranking correlation (measured by Spearman correlation) among top architec- tures of the proposed method. This is particularly important measure for effective NAS algorithms as they have to navigate the region of top models to identify the best candidates (A (Abdelfattah et al., 2021). For Few-Shot NAS, we split two edges, amounting to 42 16 sub-supernets. For GM-NAS, due to smaller branching factor (B = 2). we could afford to split four edges while keeping the total number of supernet the same as Few-Shot NAS. We train each sub-supernet using Random Sampling with Parameter Sharing (RSPS) (Li & Talwalkar, 2020), same the original Few-Shot NAS paper. Table 7 summarizes the results. The proposed method obtains 0.532 Spearman correla- tion among top 1% architectures, much higher than Few-Shot NAS (0.117). The improved ranking correlation also justifies the superior performance of GM-RSPS over Few-Shot RSPS reported in Section 4.1.
Table 7: Ranking Correlation among top architectures from NASBench-201 The proposed splitting schema leads significantly better ranking correlation than Few-Shor NAS.
Branching Factor
Spearman Correlation (p)
Method
#Splits
#Supernets
Top 0.2%
Top 0.5%
Top 1%
Few-Shot
2
0.024
0.032
0.117
16
GM (ours)
2
4
0.410
0.411
0.532
CONCLUSION
In this paper, we demonstrate that gradient similarity can effectively measure the harm of weight- sharing among child models. We propose a novel Gradient Matching NAS (GM-NAS) general- ized supernet splitting schema that utilizes gradient matching score the splitting criterion and for- mulates supernet partitioning as a graph clustering problem. Extensive empirical results across mul- tiple prevailing search spaces, datasets, and base methods show that GM-NAS consistently achieves stronger performance than its One-Shot and Few-Shot counterparts, revealing its potential to play an important role in weight-sharing Neural Architecture Search methods.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
We do not aware of any potential ethical concerns regarding our work.
ACKNOWLEDGEMENT
This work is partially supported by NSF under IIS-2008173, IIS-2048280 and by Army Research Laboratory under agreement number W91 1911NFF22-22011
REPRODUCIBILIIT STATEMENT
We provide copy of code in the supplementary material, including both search and retrain phase for our method and the reproduced baseline, to ensure reprodueibility on all search spaces. Our experimental setting is stated in Section 4, and hyperparameters described in the Appendix D. Furthermore, we also include discussions on the reproducibility of relevant baselines on DARTS and MobileNet Space in Appendix D.
REFERENCES
Mohamed S. Abdelfattah, Abhinav Mehrotra, Łukasz Dudziak, and Nicholas D. Lane. Zero-cost. proxies for lightweight NAS. In ICLR, 2021.
Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In ICMI., 2019.
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le. Understand- ing and simplifying one-shot architecture search. In ICML, 2018.
Martin Brown and Robert Smith. Directed multi oulti-objectiie optimization. International Journal of Computers, Systems, and Signals, 6(1):3-17) 17, 2005.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search target task and hardware. In ICLR, 2019.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In ICLR, 2020.
Francesco Paolo Casale, Jonathan Gordon, and Nicolo Fusi. Probabilistic neural architecture search. arXiv: /902.051 16, 2019.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. In /CML, 2020.
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. DrNAS: Dirichlet neural architecture search. In ICLR, 2021.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In ICCV, 2019.
Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In CVPR, 2019.
Xuanyi Dong and Yi Yang. NAS- AAS-Bench-201. Extending the scope of reproducible neural architec- ture search. In ICLR, 2020.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathe- matical Methods of Operations Research, 51(3):479-494, 2000.
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. arXiv: 1904.00420, 2019.
10

---

Published as a conference paper at ICLR 2022
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In CVPR, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, 2016.
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for mobile vision applications. arXiv: 1704.04861, 2017.
Shoukang Hu, Sirui Xie, Hehui Zheng, Chunxiao Liu, Jianping Shi, Xunying Liu, and Dahua Lin. DSNAS: Direct neural architecture search without parameter retraining. CVPR, 2020a.
Yiming Hu, Yuding Liang, Zichao Guo, Ruosi Wan, Xiangyu Zhang, Yichen Wei, Qingyi Gu, and Jían Sun. Angle-based search space shrinking for neural architecture search. ECCV, 2020b.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In AISTATS, 2016.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In ICML, 2013.
Guilin Li, Xing Zhang, Zitong Wang. Zhenguo Li, and Tong Zhang. StacNAS: Towards stable and consistent differentiable neural architecture search. arXiv: 1909. / /926, 2019a.
Guohao Li, Guocheng Qian, Itzel C. Delgadillo, Matthias Müllrr, Ali K. Thabet, and Bernard Ghanem. SGAS: sequential greedy architecture search. In CVPR, 2020a.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In UAI, 2020.
Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradient algorithms for neural architecture search. arXiv: 2004.07802, 2020b.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit- based approach to hyperparameter optimization. 10t::/993.11099 2019b.
Heechul Lim, Min-Soo Kim, and Jinjun Xiong. CNAS: Channel-level neural architecture search.
OpenReview, 2019. URL https:/ /pwnreviieee..ee
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In ECCV, 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In ICLR, 2019.
Renqian Luo, Fei Tian, Tao Qin, and Tin Liu. Neural architecture optimization. abs/1808.07233, 2018.
CoRR,
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. ShuffleNet V2: Practical guidelines for efficient cnn architecture design. In ECCV, 2018.
Risto Mikkullanenn, Jason Liang, Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, and et al. Evolving deep neu- ral networks. Artificial Intelligence in the Age of Neural Networks and Brain Computing, pp. doi: 10. 101 1111111667-----2--0 1---121811519991 15480-9.00015-3, URL http:/ //tp:///x..e www.dooi.oc.. 10. 10.1016/B978-00 12 818480-580000 00015-3. 3.
293-312, 2019.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In /CMI, 2018.
11

---

Published as a conference paper at ICLR 2022
Alois Pourchot, Alexis Ducarouge, and Olivier Sigaud. To share not to share: A comprehensive appraisal weight-sharing. arXiv: 2002.04289, 2020.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized evolution for image
classifier architecture search. In AAAI, 2019.
Kenneth O. Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topolo- gies. Evolutionary Computation, 10(2):9-1277, 2002.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, 2015.
Mingxing Tan and Quoc Le. EfficientNer: Rethinking model scaling for convolutional neural net- works. In ICML, 2019.
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 CVPR, 2019.
Ulrike von Luxburg. A tutorial spectral clustering. 2007.
Bochao Wang, Hang Xu, Jiajin Zhang, Chen Chen, Xiaozhi Fang, Ning Kang, Lanqing Hong, Wei Zhang, Yong Li. Zhicheng Liu, Zhenguo Li, Wenzhi Liu, and Tong Zhang. Vega: Towards an end-to-end configurable automl pipeline, 2020a.
Ruochen Wang, Xiangning Chen, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. RANK- NOSH: Efficient predictor-based architecture search via non-uniform successive halving. In ICCV, 2021a.
Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsich. Rethinking Architecture Selection Differentiable NAS. In ICLR, 2021b.
Xiaoxing Wang, Chao Xue, Junchi Yan, Xiaokang Yang, Yonggang Hu, and Kewei Sun. Mergenas: Merge operations into one for differentiable architecture search. In IJCAI, 2020b.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In ICLR, 2019.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi. Qi Tian, and Hongkai Xiong. PC- DARTS: Partial channel connections for memory-efficient architecture search. In ICLR, 2020.
Yibo Yang, Hongyang Li, Shan You, Fei Wang, Chen Qian, and Zhouchen Lin. Ista-nas: Efficient and consistent neural architecture search by sparse coding. arXiv: 2010.06176, 2020.
Quanming Yao, Ju Xu, Wei- Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In AAAI, 2020.
Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang. and Quoe Le. BigNAS: Scaling up neural archi- tecture search with big single-stage models. ECCV, 2020a.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In ICLR, 2020b.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
Miao Zhang, Huiqi Li, Shirui Pan, Xiaojun Chang, and Steven Su. Overcoming multimoo model forget- ting in one-shot nas with diversity maximization. In CVPR. 2020a.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. ShuffleNet: An extremely efficient convolutional neural network for mobile devices. In CVPR, 2018.
12

---

Published as a conference paper at ICLR 2022
Yuge Zhang, Zejun Lin, Junyang Jiang, Quanlu Zhang, Yujing Wang, Hui Xue, Chen Zhang, and Yaming Yang. Deeper insights into weight sharing neural architecture search. arXiv: 2001.01431, 2020b.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In ICLR, 2021a.
Yiyang Zhao, Linnan Wang. Yuandong Tian, Rodrigo Fonseca, and Tian Guo. architecture search. In ICML, 2021b.
Few-shot neural
Hongpeng Zhou, Minghao Yang. Jun Wang, and Wei Pan. BayesNAS: A bayesian approach for neural architecture search. In ICML, 2019.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In ICLR, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In CVPR, 2018
13

---

Published as a conference paper at ICLR 2022
APPENDIX
A PSEUDOCODE FOR GM-NAS
Algorithm summarizes the main pipeline of the proposed Generalized Supernet Splitting with Gra- dient Matching (GM-NAS). The pseudocode for our partitioning algorithm is provided separately in Algorithm for ease of reference. Note that the main difference between GM-NAS and Few-Shot NAS lies in the supernet splitting phase: Compared with Few-Shot NAS' exhaustive partitioning, GM-NAS leverages the well-motivated gradient matching score and the graph min-cut algorithm for making much more informed splitting decisions.
Algorithm 1:
Main Pipeline
Input:
The set of supernet A = {A}. warmup epochs warm_epo for supernet splitting, number of splits T', Branching factor B per split.
// supernet splitting phase
{Ao}:
forall t
, do
1)
forall A E A do
Train A for warm_epo epoch;
A' insert
GM-SPLIT(A, branch.fccto B);
end A = A';
end
// search phase 1n reinitialize w in A:
" perform architecture search on A using corresponding base methods;
Algorithm 2: Supernet Splitting with Gradient Matching, G. SPLIT(A, B)
Input: Supernet A, Branching factor forall unsplitted edge on A do forall operation o on e do temporarily enable while disabling other operations e;
evaluate A's gradient on other shared edges, averaged over mini-batcher
end
calculate the gradient matching scores based on Eqn.(2;;
compute e's importance score and operation partition based on Eqn.(3);
end
Select the edge (e*) with the best importance score to split A on;
10 From e", partition into B sub-supernets {Ap]0=1...B: return {Ao]b=1-..B
B COMPLEMENTARY ANALYSIS
B. WHAT GRADIENT TELLS ABOUT WHICH OPERATIONS SHOULD (NOT) SHARE WEIGHTS?
On NASBench-201, we find that gradient matching score always decides to assign conv_1x1 and conv 3x3 into one partition (sub-supernet), and Skip and AvgPool.3x3 into another. This behavior reasonable: High-performing architectures on NASBench-201 usually contains more parametric operations: And weight-sharing between these high performers and the rest of poor architectures could be quite harmful to the former. GM-NAS breaks the weight-sharing between high performers and the rest the architectures. This has been shown to improve the performance estimation of top models, leading to better search performance (Zhang al., 2020b).
14

---

Published as a conference paper at ICLR 2022
This is longer the case the more complex DARTS Space, where the number of parametric op- erations is less correlated with the search performance. We observe that three of the four convolution operations usually assigned to one group, while the other group consists of three non-parametric operations and one convolution. And the specific convolution operation assigned to the second group varies.
For MobileNet space consisting of structured convolution blocks, we did not observe any particular patterns in terms of how GM-NAS decides partition the supernet. Still, the superior performance of GM-NAS over Few-Shot NAS and One-Shot NAS in Table demonstrates that GM-NAS can make effective partitioning decisions on this search space.
B.2 MORE DETAILS ON THE PRELIMINARY EXPERIMENT IN TABLE 2
We provide further details for the experiment in Table 2. Given target architecture A, we construct Asim (and Adissim) by changing the operation on a randomly selected edge of A to another opera- tion that the cosine similarity between gradients computed from A and from Asim (Adissim) at shared weight are large (small). Concretely, cos (V.,, [(A; V L(Asims w.)) > 0.7 for Asim and cos( Vw,, (AA; ws), V u. [(Adissim; wi,) cos(V,, Note that the gradient similarities are computed by averaging over 100 mini-batcher after updating A together with Asim (or Adiasim) ) for 2 epochs, in order obtain a more accurate estimation. We then record and compare the training losses of A when 1) it is updated together with Asim and 2) it is updated together with Adissim for 20 epochs. The above process is repeated for 50 randomly sampled A, and the mean training losses and gradient similarities are reported in Table 2. As ex- pected, the training loss of much lower case (1) when shares weights with Agims since the training dynamics of A and Asim are similar at the shared weight.
0.3 for Adissim: where w, their shared weight.
B.3 ABLATION STUDIES ON GRAPH CUT ALGORITHMS
For all experiments in the main text, we adopt a simple graph cut algorithm with an explicit con- straint for edge/layer partitioning. Notably, the constraint term in Eqn.(3) indicates that the opera- tions are divided into roughly balanced groups. This corresponds to the balancing or normalization factor in more complex graph clustering algorithms such as Neut (von Luxburg, 2007). We do not use unconstrained graph min-cut algorithms because they tend to degenerate to trivial solutions where the algorithm simply splits one node from the rest (von Luxburg, 2007). Another reason for adopting this constraint in NAS is that we want the sub-supernets to be more balanced, as they will later be trained under identical settings. We also experiment with advanced clustering algorithms such Neut, but find that they mostly produce identical cuts to the algorithm described in Eqn.(3). We conjecture that is because empirically the gradient matching scores often lead to distinguish- able clusters, making the result insensitive to the choice of cut algorithms.
C SUPERNET SELECTION
In this section, we address the problem of deriving the final architecture from the set of partitioned sub-supernets, which we term Supernet Selection. Recall that Few-Shot NAS (and our method) splits the supernets into N sub-supernets, and then performs architecture search over these sub-supernets by training them independently from scratch before deriving a single final architecture from them.
Few-Shot NAS argues that the architecture selected from the sub-supernet with the lowest validation loss is typically the best among architectures derived from all sub-supernets. However, empirically we find that this is often not the case, especially on irregular search spaces like the cell-based DARTS Space. As shown in Table 8, for Few-Shot NAS, the architecture selected from the sub-supernet with lowest validation loss (or accuracy) does not match the top architecture from all sub-supernets (" ("max" entry in the Table). This result aligns with previous findings that the supernet's performance unrelated to the final subnetwork accuracy (Li et al., 2020a). There could be multiple potential reasons for this behavior. For example, the sub-supernet that hosts the top child architecture might also contain many mediocre architectures, so the performance of this sub-supernet as a whole might not necessarily top other sub-supernets. Moreover, after the supernet splitting phase, architecture search is performed on these sub-supernets independently, so their performance are also subject to randomness in the search phase.
15

---

Published as a conference paper at ICLR 2022
One could always evaluate each architecture derived from N sub-supermet and pick the best of them, which leads to extra overhead as . increases. To solve this, we propose to adopt Successive Halving (Karnin et al., 2013; Jamieson & Talwalkar, 2016; Li et al., 2019b) to reduce the supernet selection cost. Successive Halving progressively discards half of the poor architectures following predefined schedule, and stops until only candidate is left. For DARTS Space, schedule to (30, 100, 600), so that the overhead of retraining N
the architectures is only 2.5x that of retraining single architecture (30 8 + 70 4 + 500 2 1520 epochs). Empirically, find that varying this schedule has negligible effect on the recall of successive halving schedules, which aligns with previous discoveries on other NAS search spaces (Wang al., 2021a). As shown in Table 8, successive halving produces essentially the same results for all methods. We summarize the detailed successive halving procedure in Algorithm. 3.
Note that we only perform successive halving for the DARTS Space; and we apply it to both GM- NAS and Few-Shot NAS for fair comparisons. For MobileNet Space, we follow Few-Shot NAS and use the validation loss for supernet selection, as it produces good enough results and speedup the experiments.
Table 8: Performance comparison among derived child networks using different supernet selection criteria in Few-Shot NAS and GM-NAS
Test Error(% %
Method
Supernet selection criterion
Best
Avg
validation accuracy validation loss
2.74
2.88-10.15
2.53
2.73+1.21
Few-Shot DARTS (1st)
max successive halving
2.48
2.60:10.10
2.48
2.60
validation accuracy
2.45
2.73
validation loss
2.45
2.68=0.11
GM-DARTS (1st)
max successive halving
2.35
2.46=10.7
2.35
2.407
validation accuracy
2.83
3.00=10.16
validation loss
3.25
3.42:10.11
Few-Shot DARTS (2nd)
max successive halving
2.58
2.63:10.06
2.58
2.03
validation accuracy
2.57
F..11
validation loss
2.59
2.68++0.08
GM-DART'S (2nd)
max successive halving
2.40
2.49-10.08
2.40
2.49-10.08
validation accuracy
2.49
3.25
validation loss max successive halving
2.88
3.32-10.4
Few-Shot SNAS
2.62
2.70-10.05
2.62
2.70+10.05
validation accuracy
2.49
2.70
validation loss
2.49
2.72+:0.20
GM-SNAS
max
2.34
2.55+0.11
successive halving
2.34
2.55
16

---

Published as a conference paper at ICLR 2022
Algorithm 3: Supernet Selection via Successive Halving
Input: candidate pool [P] with N child networks derived from N sub-supernets, checkpoint schedules ckpts = {epo1, epo2, epor]
Result: a single network from P
epoch epo = 1;
while P| > do
train each network in P for one epoch epo + 1;
epo E ckpts then
calculate the validation accuracy for each network in P: discard the bottom half of networks from based on their validation accuracy;
end
return the architecture left in P:
D IMPLEMENTATION DETAILS
D.1 NASBENCH-201
For experiments in Section 4.1, set the warmup epoch 15 for DARTS and SNAS, and 20 for RSPS as its single path nature requires longer training (Zhang et al., 2020a). We then perform architecture search each sub-supernet for 30 epochs (50 for RSPS) following the protocol of the corresponding base algorithms. The search is conducted on three datasets separately for four random seeds. For all methods, we select the best architecture from the sub-supemets the final architecture.
D.2 DARTS SPACE
Supernet Partition During the supernet (with 8 cells) splitting phase, we set the warmup epoch 2, the number of splits 3, and the branching factor 2. After the supernet splitting phase is finished, we conduct architecture search on the generated sub-supernets for 15 epochs. This way, the total number of epochs each of the 7 sub-supernets for 20-25 epochs according to the author).
1 1 + 2 #4+ 15
134, similar to Few-Shot NAS (train
Supernet Selection After searching architectures on each sub-supernet, we apply the successive halving (Appendix C) select the top-performed child network derived from eight sub-supernets.
Retraining settings (architecture evaluation) To establish fair comparison with prior arts, strictly follow the retrain settings of DARTS (Liu et al., 2019) to evaluate the searched architecture. Coneretely, we stack 20 cells to compose the final derived architecture and set the initial channel number as 36. The derived architecture is trained from scratch with a batch size 96 for 600 epochs. We use SGD with an initial learning rate of 0.0025, momentum of 0.9, and weight decay of 3 x 10 and a cosine learning rate scheduler, In addition. we also deploy the cutout regularization with length 16, drop-path with probability 0.3, and an auxiliary tower of weight 0.4.
Reproducing Few-Shot NAS Baseline Since Few-Shot NAS does release its search code for the DARTS Space, we follow the search settings in the original Few-Shot NAS paper to reproduce its result: We randomly select one edge and split the supernet into 7 sub-supernets, and conduct architecture search on each sub-supernet for 20 epochs. For a fair comparison with GM-NAS, we also use the successive halving (Appendix C) select the best architecture from these sub-supernets. The reproduced results we obtain for Few-Shot DARTS is 2.48% (the best column in Table 4). This worse than the one reported in Few-Shot NAS (2.31%) because Few-Shot NAS uses its own retraining protocol to train and evaluate their search architecture, rather than the DARTS' protocol widely adopted by previous methods (confirmed with the author). Evaluating their released best architecture under DARTS protocol results in 2.44% test error, similar (2.48%). Nonetheless, GM DARTS achieves 2.35% error rate on DARTS, substantially lower than both of these numbers.
reproduced result
17

---

Published as a conference paper at ICLR 2022
D.3 MOBILENET
GM ProxylessNAS / OFA For both ProxylesSNAS and OFA, we set the warmup epoch of GM- NAS to 40. We perform split the supernet twice in total, and set the branching factor to 2 for the first split and 3 for the second split, so that the resulting number of sub-supernets match that of Few-shot NAS. After the supernet partitioning phase, for GM ProxylessNAS, we use the same search settings as ProxylessNAS, except for setting the number of search epochs to 40; For GM OFA, we also follow the same search settings as the original paper.
Supernet Selection As mentioned in Appendix C, for Mobilenet Space, we select the sub-supernet with the lowest validation loss and derive the best architecture from this supernet, same as Few-Shot NAS.
Retraining settings (architecture evaluation) For ProXylessNAS, we follow the settings of Few- Shot ProxylessNAS (Zhao al., 2021b; Cai al., 2019) train our discovered architecture. Since the architecture evaluation codes for OFA (finetune) and Few-Shot OFA (retrain) are not released, we also use the setting of Few-Shor ProxylessNAS train and evaluate the derived architecture of OFA (reproduced), Few-Shot OFA (reproduced), and GM-OFA.
Reproducing OFA and Few-Shot OFA baseline OFA (Cai et al., 2020) does not release the predictor training and child network finetune code. So follow the settings of Few-Shot Proxy- lessNAS to reproduce the OFA result. Our reproduced accuracy is 79.7%, comparable to the one (80.0%) reported in the OFA paper.
Few-Shot NAS (Zhao et al., 2021b) also does not release their code and the searched architectures on OFA. We try best reproduce their result by communicating with the author, but still not able to reproduce the reported 80.5% accuracy on ImageNet. One potential reason could be that Few-Shot NAS an unreleased powerful teacher network train the derived architectures. Since we could not obtain this teacher network, we follow the Few-Shot ProxylesNNAS setting described above train and evaluate searched architectures for OFA, Few-Shot OFA, and our methods with the teacher model released in Wang et al. (2020a). The reproduced numbers are reported in Table 5.
E SEARCHED ARCHITECTURES
(a) Normal Cell
(b) Reduction Cell
Figure 3: Normal and Reduction cells discovered by GM-DARTS (Ist, seed 0) on CIFAR-10 on DARTS Space
18

---

Published as a conference paper at ICLR 2022
c.
ma Repoomect
(b) Reduction Cell Figure 4: Normal and Reduction cells discovered by GM-DARTS (Ist, seed 1) on CIFAR-10 on DARTS Space
Normal Cell
(a) Normal Cell
(b) Reduction Cell
Figure 5: Normal and Reduction cells discovered by GM-DARTS (1st, seed 2) CIFAR-10 DARTS Space
2
Mip coeRac
c.
pool
E-b-1
(a) Normal Cell
(b) Reduction Cell
Figure 6: Normal and Reduction cells discovered by GM-DARTS (1st, seed 3) on CIFAR-10 on DARTS Space
Alip comnact
(2-3)
Set_atev.3cc
skip connt
(a) Normal Cell
(b) Reduction Cell
Figure 7: Normal and Reduction cells discovered by GM-DARTS (2nd, seed 0) on CIFAR-10 on DARTS Space
19

---

Published as a conference paper at ICLR 2022
reat joot
dep connect
(0
Up
2-8-11
mas poot
K0,001 36
(b) Reduction Cell Figure 8: Normal and Reduction cells discovered by GM-DARTS (2nd, seed 1) on CIFAR-10 on DARTS Space
(a) Normal Cell
(a) Normal Cell
(b) Reduction Cell
Figure 9: Normal and Reduction cells discovered by GM-DARTS (2nd, seed 2) on CIFAR-10 on DARTS Space
Edol
L.
Edolt
(a) Normal Cell
(b) Reduction Cell
Figure 10: Normal and Reduction cells discovered by GM-DARTS (2nd, seed 3) CIFAR-10 DARTS Space
20

---

Published as a conference paper at ICLR 2022
max max__poo______ pool_3x3 3x.
max moix__ooo___g 333
sep_cony 5x5
c_tk-2)
max 3x3
c_(k)
pax__ool_3x3
c_ik-13
max_pooo___ 3x3
max pool_ max_pool___ 3x3
2.00
max pool
Normal Cell
(b) Reduction Cell
Figure 11: Normal and Reduction cells discovered by GM-SNAS (seed 0) on CIFAR-10 10 on DARTS Space
2.N1
Normal Cell
(b) Reduction Cell
Figure 12: Normal and Reduction cells discovered by GM-SNAS (seed 1) on CIFAR- 10 on DARTS Space
-JKI
20
k.b
Normal Cell
(b) Reduction Cell
Figure 13: Normal and Reduction cells discovered by GM-SNAS (seed 2) on CIFAR- 10 on DARTS Space
(-4 Fat Pac
(a) Normal Cell
(b) Reduction Cell
Figure 14: Normal and Reduction cells discovered by GM-SNAS (seed 3) CIFAR- 10 on DARTS Space
21

---

Published as a conference paper at ICLR 2022
MB1 3X3
MB6 7X7
MB6 5XS
Mes 5XS
MB6 SXS
MB6 7X7
MB6 5X5
M86 3X3
MB6 3X3
MB6 5XS
MB6 3X3
MB6 3X3
MB6 3X3
MB6 7X7
MB6 7XX
MB6 7X7
MBS 7X7
MBs 3x3
MB6
MB6
Figure 15: Architecture discovered by GM-ProxylessNAS on ImageNet MobileNet Space
Conv 3x3
MB4 xx7
MB3 5x5
MIB3 3x3
MBB 5x5
M134 3x3
MB4 3x3
MB6 3x3
MB6 3X3
MB6 7x7
MB4 7x7
MB6 3x3
MB3 3x3
MBB 3x3
MB6 3x3
MB4 3x3
MB6
MB&
MB6
Figure 16: Architecture discovered by GM-OFA (Large) on ImageNet on MobileNet Space
22

---

Published as a conference paper at ICLR 2022
F ABLATION STUDY ON THE NUMBER OF SPLITS
We conducted extra ablation study on how the number of splits affect the search outcome of the proposed method using NASBench-201 and CIFAR-I0. As showing in Figure 17, GM+DARTS reaches near oracle search performance with only two splits. Splitting one more time pushes the performance further, but may not worth the extra search cost.
Performance GM+DARTS NASBench-201 under various T
100
Global Optimum
80
Text Aczuracy
80
70
60
DARTS
Our Choice (for 201)
Total fedges
Figure 17: Search performance of GM+DARTS on NASBench-201 and CIFAR-10 10 under different number of splits T. GM-NAS reaches oracle performance with T 2. Increasing T further brings diminishing return w.r.t. the search cost. All experiments are repeated with four random seeds.
Further ablation study was also conducted in OFA by adding more search budget to GM+OFA on the ImageNet task. We select three layers (T = 3) to perform the supernet partitioning, and divide operations on each selected edge into two groups (B 2). As shown in Tab. 9, this improves GM+OFA further, leading to test error of 19.4%, which is 0.9% better than OFA and 0.8% better than Few-Shot OFA.
Table 9: Search performance of GM-OFA on ImageNet by adding more search budget
Method
Top-1 Test Error(%)
Improvement over OFA baseline
OFA (reproduced)
20.3
Few-Shot OFA (reproduced)
20.2
0.1% %
GM OFA (ours)
19.7
0.6%
GM OFA w/ more search budget (ours)
19.4
0.9%
23


Reviews:
[{"review_id": "uKM_CwTaixZ", "reviewer": "Reviewer_Y8nY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and easy to follow. I appreciate the efforts made by this paper on alleviating the weight-sharing problem in one-shot NAS approach by proposing a more reasonable few-shot NAS method from a supernet-splitting perspective. Without many bells and whistles, the proposed method also demonstrates consistent performance gains over its counter-part algorithms.\n\nThough promising, I have three main concerns about this paper:\n\n1, According to section 3.4, greedy algorithm is employed for edge selection, where in each split phase only the edge with maximum sum of GM score is considered to be split. I am doubtful about this specific design because the multi-step split process constitutes a decision chain where local-only criterion usually does not serve for the global purpose. I am willing to see more theoretical (or at least experimental) justification/analysis on this part.\n\n2, All supernet (search space) involved in this paper have orders magnitude more number of edges than three (i.e. the number of edges to be split). Does it suggest the proposed approach can only slightly reduce the weight-sharing extent in the scope of whole supernet? If so, why the searched architectures are extremely close to the optimal one (e.g., Table 3) . \n\n3, There are no ablation studies on the performance changes w.r.t. the different settings of \nT\n without considering search cost. It might serve as an important indicator to help understand how much extent the weight-sharing affects the sub-network evaluation accuracy and might also provide some hints for my last question.\n\nOther minors:\n\n1, What is the Random (baseline) method in Table 3. Does it refer to the random partition?\n\n2, Missing T and B settings for NASBENCH-201.", "summary_of_the_paper": "This paper improves the sub-supernet splitting strategy in few-shot NAS with a gradient matching (GM) score. During supernet optimization, the GM explicitly computes the \"agreements\" among different operations on an edge in the supernet, which is then treated as the criterion to split those most mismatched operations into different sub-supernets. Although the basic intuition makes some good points and is easy to grasp, I have several concerns on the methodology and the experimental designs of this paper. ", "summary_of_the_review": "This paper presents a new partition strategy for few-shot NAS, which empirically seems to be a more efficient solution to alleviate the weight-sharing problem in one-shot NAS. The intuition/algorithm details are well demonstrated and the experimental evaluation is clearly stated.\nOverall I believe the quality of this paper has met the bar of ICLR community, but my concerns about the justifications for its technical designs and some numerical results make me indecisive on posing an acceptance. \n\nI would like to raise my rating if authors properly address my concerns.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YV9W-tnjbRH", "reviewer": "Reviewer_tbrG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Pros:\n1. This work answers two questions about how to partion supernets in Few-Shot NAS: 1) Is exhaustive-splitting good? 2) How to partion is better? I think this work has basically answered the above two questions.\n2. This work proposes a partioning criteria based on gradient-matching score and formulate the splitting as a graph clustering problem. This partioning method further improves the performance of Few-Shot NAS and  the derived GM-NAS outperforms its Few-Shot and One-Shot counterparts while surpassing previous comparable methods in terms of the accuracy of derived architectures.\n\n### Cons:\n1. I don’t quite understand what is the meaning of showing Train Loss in Table 2? Low Train Loss does not mean that the accuracy of the model on the validation set is high. I think you should show the effect of share weight on the model’s performance on the validation set under different Grad Similarity conditions.\n2. I don't quite understand why the size of  $\\mathcal{U}$ should be restricted in Eqn.(3)?\n\n### Some typos: \n1. On the left of Table 2 in Section 3.3, lowercase should be used after the semicolon.\n", "summary_of_the_paper": "This work is a further exploration in the direction of Few-Shot NAS. It proposes a method of partioning supernet based on gradient-matching score. Compared with the method based on exhaustive-spltting, the method proposed in this paper can achieve better results. Its contributions are as follows:\n\n1. Point out the problem based on exhaustive-splitting method;\n2. A partioning method based on gradient-matching score is proposed, and this method can achieve good results on multiple search spaces and datasets.", "summary_of_the_review": "Overall, I vote for accepting. First, the overall logic of the paper is relatively clear, basically answering two questions in Pros of **Main Review**. In addition, I think it is reasonable to consider the supernet partition problem from the perspective of gradient, and this work proves the effectiveness of this method through experiments. Hopefully the authors can address my concerns in the rebuttal period. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EWXlsOS-rb", "reviewer": "Reviewer_x5Hy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The studied direction is important that we need to endow NAS algorithms quickly adapting to new tasks or data. The work takes a step further based on previous methods. It carefully examines the potential effectiveness improved by grouping operations. The introduced techniques are resonable, like gradients matching, cosine distance, and etc. Overall the paper is very easy to follow and the Figure 2 clearly shows what parts of the problem the method focused on.\n\nIn addition, this paper conducted extensive experiments, especially on the comparisons with previous methods, including DARTS, RSPS, SNAS, ProxylessNAS, and OFA and search spaces NASBench-21, DARTS, and MobileNet Space. On three benchmark datasets, it achieved consistent improvements and some of them are significant (Table 3,4,5). Several ablation studies are also conducted, including comparing different similarities measures, edge selection, warmup epoch numbers, and restart.\n\nThe reviewer especially likes Appendix B.1 and E where give some instances of the method and the reader can have a certain high-level sense regarding the method. Probably, can also mention some of the contents in the main paper.\n\nRegarding negative points, the reviewer mainly doubts the novelty of the paper since it focused on a small part of the whole problem by utilizing existing tools. Also, the reviewer didn't see many around cost comparisons in the main paper, like time and paranum.\n\nFurthermore, the paper used a very simple algorithm for graph splitting. Probably, more discussion and implementations should be introduced here and add them into the ablation section.\n\n\n-----------------------------after rebuttal---------------\n\nThe reviewer thanks the authors' efforts. Yes, it is figure 1, and the reviewer is sorry for the missing points. But, the reviewer doesn't get convinced by the arguments about the novelty. This work currently studied a relatively small point with existing techniques. It is ok to be accepted, but the reviewer will not fight for it. Also, as the author said, they focused on the splitting criterion, and thus, the reviewer encourages the author to add more comprehensive studies around the graph splitting algorithm. ", "summary_of_the_paper": "This paper proposed a method for few-shot NAS tasks. It found some operations may behave similarly and can be grouped into one and others may not. Those patterns should be considered to save the computation as well as improve accuracy. It proposed a graph construction and spitting pipeline to achieve the goal. Specifically, they used gradient matching and cosine distance to construct the graph among layers. Then, splitting the graph by solving a graph clustering problem. \n\nIt conducted experiments on three benchmarks (cifar10, cifar100, and ImageNet) over three search spaces (NASBench-201, DARTS, MobileNet Space) and compared with various baselines. The results show the strength of the proposed method. ", "summary_of_the_review": "Overall, the reviewer thinks the paper is solid while lacking some novelty. The reviewer appreciates the details mentioned in both the main paper and the appendix.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2mku83VXFpb", "reviewer": "Reviewer_dVgX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros\n++ The paper identifies a drawback of the vanilla few-shot NAS, which is the exhaustive partitioning. \n++ The paper provides a criterion, ie. graph min-cut on the gradient similarity between operations, to partition the (sub-)supernet. \n++ Some toy examples (Table 1 and 2) are provided to support the claim of the paper regarding (1) the necessity of designing a partitioning rule and (2) that the gradient similarity is highly related to the search quality.\n++ Extensive experiments show that it is better than the vanilla few-shot NAS. Moreover, it is shown in the ablation study that the ranking correlation in indeed improved by the proposed splitting criterion (Table 7).\n\nCons\n-- The experiments of the proposed GM are mainly designed to match the search budget of few-shot NAS for a fair comparison. But how about the performance of GM when more or less search budge is considered? For example in Table 5, what would happen if less search costs are used when combined with proxylessNAS? Also, what would happen if more search costs are used when combined with OFA_Net?\n-- What is the performance of GM+DARTS and GM+SNAS on ImageNet?\n-- The improvement over OFA_Net in Table 5 is marginal. ", "summary_of_the_paper": "This paper aims at improving few-shot NAS by proposing a gradient-guided schema to partition the supernet into sub-supernets during the search. The proposed splitting criterion is based on the cosine similarity between the gradients from different child models. Namely, child models that have similar gradients are more likely to be grouped together without splitting, so as to save computational costs and to allow the splitting of more layers than the vanilla few-shot NAS, achieving better performance. Extensive experiments show its superiority over the few-shot NAS.", "summary_of_the_review": "Overall, it is a paper of good quality. I lean toward accepting the paper because of the intuitive splitting rule proposed in the paper and the supportive results. I will consider raising the rating if the authors can address my above-mentioned questions regarding the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers give acceptance scores. 
One reviewer also commented that they would like to increase their score from 6 to 7 (which isn't possible in the system).
I encourage the authors to add the substantial new results generated during the rebuttal into the paper.
Decision: Accept (Poster)