Neighborhood-Aware Neural Architecture Search
Authors: Xiaofang Wang
Shengcao Cao
Mengtian Li
Kris M. Kitani
Venue:  (2021)
Keywords: Neural architecture search
Flat minima

Abstract: Existing neural architecture search (NAS) methods often return an architecture with good search performance but generalizes poorly to the test setting. To achieve better generalization, we propose a novel neighborhood-aware NAS formulation to identify flat-minima architectures in the search space, with the assumption that flat minima generalize better than sharp minima. The phrase ``flat-minima architecture'' refers to architectures whose performance is stable under small perturbations in the architecture (\emph{e.g.}, replacing a convolution with a skip connection). Our formulation takes the ``flatness'' of an architecture into account by aggregating the performance over the neighborhood of this architecture. We demonstrate a principled way to apply our formulation to existing search algorithms, including sampling-based algorithms and gradient-based algorithms. To facilitate the application to gradient-based algorithms, we also propose a differentiable representation for the neighborhood of architectures. Based on our formulation, we propose neighborhood-aware random search (NA-RS) and neighborhood-aware differentiable architecture search (NA-DARTS). Notably, by simply augmenting DARTS~\cite{liu2018darts} with our formulation, NA-DARTS finds architectures that perform better or on par with those found by state-of-the-art NAS methods on established benchmarks, including CIFAR-10, CIAFR-100 and ImageNet.

Under review as a conference paper at ICLR 2021
NEIGHBORHOOD-AWARE NEURAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Existing neural architecture search (NAS) methods often return an architecture with good search performance but generalizes poorly to the test setting. To achieve better generalization, we propose a novel neighborhood-awee aware NAS formulation to identify flat-minima architectures the search space, with the assumption that flat minima generalize better than sharp minima. The phrase "flat-minima archi- tecture" refers to architectures whose performance is stable under small pertur- bations in the architecture (e.g., replacing convolution with skip connection). Our formulation takes the "flatness" of an architecture into account by aggregat- ing the performance over the neighborhood of this architecture. We demonstrate a principled way to apply our formulation to existing search algorithms, includ- ing sampling-basee
algorithms and gradient-based algorithms. To facilitate the application to gradient-basee algorithms, we also propose a differentiable repre- sentation for the neighborhood of architectures. Based on our formulation, we propose neighborhood-aweer differentiable architecture search (NA-DARTS), Notably, by simply augmenting DARTS (Liu et al.] (019)) with our formulation, NA-DARTS finds architectures that perform better or on par with those found by state-of-the-an NAS methods on established benchmarks, including CIFAR-10, CIFAR-100 and ImageNet.
random search (NA-RS) and neighborhood-aww -warr
INTRODUCTION
The process of automatic neural architecture design, also called neural architecture search (NAS), is promising technology improve performance and efficiency for deep learning applications (Zoph) & Le 2017 Zoph et al., 2018: Liu et al., 2019). NAS methods typically minimize the validation loss find the optimal architecture. However, directly optimizing such an objective may cause the search algorithm to overfit to the search setting, i.e., finding a solution architecture with good search performance but generalizes poorly the test setting. This type of overfitting
result of the differences between the search and test settings, such as the length of training schedules (Zoph & 2018).
Le 2017 Zoph et al., 2018), cross-architecture weight sharing (Liu et al., 2019; 9 Pham et al.
and the usage of proxy datasets during search (Zoph & Le. 2017 Zoph et al.) 2018 Liu al.
2019
To achieve better generalization, we propose novel NAS formulation that searches for mflat-minima architectures". which we define architectures that perform well under small perturbations of the architecture (Figure []. One example of architectural perturbations is to replace a convolutional operator with skip connection (identity mapping). Our work takes inspiration from prior work on neural network training, which shows that flat minima of the loss function correspond to network weights with better generalization than sharp ones (Hochreiter & Schmidhuber 1997). We show that flat minima in the architecture space also generalize better to a new data distribution than sharp minima (Sec. 3.3
Unlike the standard NAS formulation that directly optimizes single architecture performance, i.e., a' arg min f(a), we optimize the aggregated performance over the neighborhood of an architecture:
arg min (f())
aEA
where f(-) is a task-specific enror metric, a denotes an architecture in the search space A. (aaa) denotes the neighborhood of architecture o, and g(.) is an aggregation function (e.g., the mean

---

Under review as a conference paper at ICLR 2021
Validation Loss
Validation Loss
6.9
670
032
0.0
A1
(a) Standard formulation
(b) Neighborhood aware formulation
Figure 1: Loss landscape visualization of the found architecture. We project architectures (instead of the network weights) onto a plane. The architectures are sampled along two prominent direc- tions (the two axes, Å and A1), with (0, 0) denotes the found architecture. We see that our found architecture (right) is much flatter minimum than that found with the standard formulation (left). We provide visualization details in the appendix.
function). Note that overload the notation of the error metric f()) and define f(-) to return of errors when the input is a set architectures the neighborhood: f(N(a)) = (f(a') a' E M(a)). Common choices for f(-) are validation loss and negative validation accuracy. We will discuss more details of neighborhood (a(a) and aggregation function g(-) in the following text.
To implement our formulation, tion function g(-). How to define the neighborhood of an architecture is an open question. One possible method obtain neighboring architectures is to perturb one or more operations in the ar- chitecture and the degree of perturbation defines the scope of the neighborhood. This method can be applied sampling-hai
must define the neighborhood N(a) and specify aggrega-
search algorithms, e.g., random search and reinforcement learning- However, it cannot be directly used to generate neighboring architectures for gradient-based search algorithms (a.ka, differentiable NAS), where the neighboring architectures themselves also need to be differentiable with respect to the architecture being learned. To address this issue, propose a differentiable representation for the neighborhood of architectures, which makes the objective function differentiable and allows to apply our formulation to gradient-based algorithmss, e.g., DARTS (Liu et al. 2019). Properly choosing the aggregation function g(-) can help the search al- gorithm identify flat minima in the search space. Our choice of g(-) (e.g.. mean) is inspired by the definition of the flatness/sharpness of local minima in previous work (Chaudhari et al. 2017 Keskar al. 2017 Dinh et 2017).
We summarize our contributions as follows:
1. We propose neighborhood- NAS formulation based on the flat minima assumption, and demonstrate a principled way to apply our formulation to existing search algorithms, including sampling-based algorithms and gradient-based algorithms. We empirically validate our assumption and show that fat-minima architectures generalize better than sharp ones.
2. We propose a neighborhood-awaan random search (NA-RS) algorithm and demonstrate its superiority over the standard random search. On
(Dong & Yang 2020),
NA-RS outperforms the standard random search by 1.48% on CIFAR-IOK 100 and 1.58% on ImageNet- MongeNet-161120 12-000.
3. We propose differentiable neighborhood representation that tion to gradient- NAS methods. We augment DARTS (Liu et al. 2019) with our formu- lation and name the proposed method NA-DARTS. Our NA-DARTS outperforms DARTS by 1.18% on CIFAR-100 and 1.2% on ImageNet, and also performs better than or on par with state-of-the-art NAS methods.
apply formula-
2 RELATED WORK
Flat Minima. Hochreiter & Schmidhuber (1997) shows that flat minima of the loss function of neural networks generalize better than sharp minima. Flat minima used to explain the poor gen- eralization of large-batel methods (Keskar et al. [0177] Yao et al. 2018). where large- methods shown to be more likely converge sharp minima. Chaudhari et al. (2017) propose ob-
2

---

Under review as a conference paper at ICLR 2021
jective function for training neural networks that flat minima preferred during optimization. Their objective can be interpreted as a weighted average of the (transformed) function values of data points around the local minima, which inspires us to consider mean as of the aggregation func- tions. Previous work mentioned above focus on flat minima in the network weight space. However, study flat minima in the architecture space, which is discrete and fundamentally different from the continuous weights studied in previous work. This makes it non-trivial to apply the flat minima idea to NAS.
Zela et al. 2220)) observes a strong correlation between the generalization error of the architecture found by DARTS (Liu et al. 2019) and the flatness of the loss function at the found architecture. They propose several regularization strategies to improve DARTS, such as early stopping before the loss curvature becomes too high. Our flat minima assumption is motivated by their observation and our method can be combined with their regularization strategies.
NAS -Sarhh Algorithm. Various search algorithms have been applied to solve NAS, including sampling-based and gradient-based algorithms. Representative sampling-basete algorithms include random search (Li & Talwalkar 2019), reinforcement learning (Baker et al. 2017] Zoph & Le| 2017
Zoph et al. 2018; Zhong et al., 2018), Bayesian optimization (Kandasamy et al. 2018 Cao et al.
2019), evolutionary algorithms Xie & Yuille 2017 Real et al. 2017] 2019), and sequential model-
based optimization (Liu et al.
2018). To make NAS more computationally efficient, weight sharing
across architectures is proposed to amortize the training cost of candidate architectures (Pham et al,,
2018 Bender al.] 2018). Based on weight sharing, gradient-basee algorithms are proposed to directly learn the architecture with gradient descent (Liu et al., [019 Xie et al., 2019). Our focus is not proposing novel search algorithms but revisiting the standard NAS formulation. Our proposed formulation can be applied to both sampling- based algorithms and gradient-based algorithms.
NAS Search Space. Search space crucial for the performance of NAS. One of the most widely used search spaces is the cell search space (Zoph et al. 2018), which searches for cell that can be stacked multiple times to form the entire network. Our proposed neighborhood-aww -warre formulation is agnostic to the search space, and we specifically showcase our formulation on the cell search space.
NEIGHBORHOOD FORMULATION
We propose a neighborhood-aware NAS formulation (Eq. D to identify flat minima in the search space. Our formulation builds upon the assumption that flat-minima architectures usually generalize better than sharp ones. In this formulation, the optimal architecture is selected according to the ag- gregated performance g (a)) of neighbors of architecture, instead of the standard criterion, Le., single architecture performance f(o:) only. We now introduce the neighborhood definition of an architecture (aa) and the aggregation function 9())-
3.1 NEIGHBORHOOD DEFINITION AND CELL SEARCH SPACE
Formally defining the neighborhood requires distance metric between architectures, which largely depends on how an architecture is represented and how the search space is constructed. We adopt the cell search space (Zoph et al., 2018) as it has been widely used in recent NAS methods (Liu et al,, 2018 2019). Instead of the entire architecture, we search for a cell that can be stacked multiple times to form the entire architecture. The number of times the cell stacked and the output layer are manually defined prior to the search.
A cell is defined as a directed acyelic graph (DAG) consisting of nodes. Each node represents feature map. Each directed edge (i.j) < i < j S n) is associated with operation used to transform the feature map at node i, and passes the transformed feature map to node j. The feature map at one node is the sum of all the feature maps on the incoming edges to this node: rff)) EGSEER Ete o% (i.j) (x(())), where denotes the set of edges in the cell, x:(() is the feature map at node i, and o% is the tt operation among the available operations. (i-)) is m-dim one-hot vector, indicating the operation choice for edge (i,j)- A cell is then represented by a set of variables a = (f.). Note that (i.5) being a one-hot vector means that only one operation is chosen for edge (i.j). On a side note, the one-hot constraint on (f-J) can be relaxed in differentiable NAS methods (Liu et al. 2019 Xie al. 2019)
3

---

Under review as a conference paper at ICLR 2021
We define the distance between two cells and a' as:
dist(a, a') E (WIEE
o(alt)) a ((55)))
where 6(,-) is the total variation distance between two probability distributions: d(p, q) = allp 9//1 -k=1 Ipt 9k/- Here p and q are both m-dim probability distributions. The total variation distance is symmetric and bounded between and It also offers the following property: 8(a! , ((.))) = 0 implies that the two cells have the same operation at edge (i.j) and implies that they have different operations at edge (i,j). Note that instead of directly counting the edge differences, we adopt total variation distance to accommodate relaxed that is later used differentiable NAS methods (Liu et al., 2019 Xie et al. 2019).
((a(5,)) ((al),))a""))))
The neighborhood of cell a is defined as:
N(a) {a' disst(a,a') S dd,
where d is a distance threshold. Due to the property of the total variation distance, when is an integer, the neighborhood contains all the cells that have at most d edges associated with different operations from a. For clarification, our definition of neighborhood includes the reference architec- ture itself.
3.2 AGGREGATION FUNCTION
Given an architecture a, the flatness its neighborhood is determined by how much the performance (e.g., validation loss) of its neighboring architectures varies compared to a itself. Intuitively, when is a flat minimum, its neighboring architectures should perform similarly to a. However, when a sharp minimum, the loss of architectures around a increases drastically compared to a.
Based on this intuition, we set g(-) as the mean function, since the mean validation loss of ar- chitectures around flat minimum expected to be lower than those around a sharp minimum. Importantly, minimizing mean (f()(a)) ensures that a is local minimum and at the same time has a flat neighborhood. For a similar reason, median and max are also valid choices for g(-) to dif- ferentiate between flat minima and sharp minima. We provide more discussions of the aggregation function in the appendix.
3.3 JUSTIFICATION OF FLAT MINIMA ASSUMPTION
3.3.1 FLAT MINIMA GENERALIZE BETTER
Flat minima in the network weight space shown generalize better than sharp ones (Hochreiter & Schmidhuber, 1997). However, we focus on flat minima in the architecture space, which is discrete and fundamentally different from the continuous weights studied in previous work. So we conduct experiments on NAS-Bench-201 (Dong & Yang 2020) to verify that flat minima in the architecture space also generalize better.
NAS-Bench-201 provides simulated environment for NAS experiments. Using NAS- 10S-Bench-201, we search on CIFAR- 10 and evaluate the found architectures not only on CIFAR-10, but also on CIFAR- 100 and 1mageNeet1161222 120 to better assess the generalization performance of architectures. We select 100 architectures from 10 to represent local minima in the search space. Next, we show that among these local-minima architectures, flat minima outperform sharp ones, especially on CIFAR- 100 and ImageNet-16-120.
that have the lowest validation error on CIFAR-
We measure the flatness of each local-minimum architecture with its neighborhood variance: the variance the search-time validation error of neighhoring architectures on CIFAR-10. Based on their neighborhood variance, divide the 100 architectures into 2 groups: (1) flat minima, which are the 50 architectures with flat neighborhood (low neighborhood variance), and (2) sharp minima, which are the other 50 architectures with sharp neighborhood (high neighborhood variance).
We observe that the average search-time validation error of flat minima and sharp minima are almost the same (14.55% and 14.57%). But, shown in Table la] the average test error of flat minima is lower than sharp minima on all three datasets, especially on CIFAR- (1.10%) and ImageNet-16. 120 (1.2 11.4%.). This verifies that flat minima generalize better.
4

---

Under review as a conference paper at ICLR 2021
Table 1: Left: Average test eπrоr of flat-minima architectures and sharp-minima architectures. Flat minima consistently outperform sharp minima on all three datasets. Right: Kendall's s Tau (rank correlation) of the standard criterion f(a) (baseline) and our criterion g (f(N()))). Our criterion gives more accurate ranking of architectures on all three datasets.
(a)
(b)
CIFAR-10
CIFAR- 100
ImageNat- 16: 120
CIFAR-10
CIFAR-I0 100
ImageNeet166122
Flat minima
6.23
28.90
55.17 56.41
Baseline
0.66 +: 0.03
0.66 + 0.02
0.61 0.03
Sharp minima
6.66
30.00
Ours
0.76 + 0.03
0.77 + 0.03
0.74 + 0.03
3.3.2 AGGREGATED PERFORMANCE GIVES BETTER RANKING OF ARCHITECTURES
Based on the flat minima assumption, our neighborhood -awae formulation suggests using the ag- gregated performance g of (f)) the criterion to select optimal architectures, instead of the standard criterion f(a). The selection criterion determines whether we can obtain an accurate rank- ing of candidate architectures during search, and further determines the performance of found archi- tectures. We show that our criterion g (J (J))())) ranks architectures more accurately than s(x).
We evaluate the ranking estimated by criterion 9 (f(A(a))) the standard criterion f(a) on NAS-Bench-201. Following Yu et al, (2020), we use the the Kendall's Tau metric (the higher the better) to measure the correlation between the estimated ranking and ground truth ranking of archi- tectures. As the ground truth ranking is specific to each dataset, we evaluate the estimated ranking on the three datasets separately. From Table lb] we see that our criterion g (f(N(a))) (g(+) mcan) ranks architectures much more accurately than the standard criterion f(a). Due to space constraint, we include experimental details and more results of other aggregation functions in the appendix.
NEIGHBORHOOD-AWARE SEARCH ALGORITHMS
We propose neighborhood-awee random search and neighborhood-awarn DARTS by applying our formulation to random search (sampling-hase and DARTS (gradient-based) respectively.
4.1 NEIGHBORHOOD-ANEE
RANDOM SEARCH
When applying our formulation to random search, we only need to change the criterion of selecting optimal architectures from f(a) to the aggregated performance g (f()))))). At cach step, ran- domly sample an architecture a and compute its aggregated performance (f))))))), and choose the one with the best aggregated performance as our solution. We provide detailed algorithm sketch of niihhborhood-awarc random search (NA-RS) in the appendix.
In practice, the entire neighborhood may be large. Instead of using all the neighbors, we sample subset of Pahr neighboring architectures from the neighborhood. In our implementation, we always include the reference architecture itself in the sampled subset.
Note that since NA-RS evaluates neighborhood of architectures at each step, for fair comparison, allow the standard random search (baseline) to run for more steps such that the two methods evaluate the same number of architectures during search. Specifically, if our NA-RS searches for T steps, the standard random searches for T Nahr steps.
While we only present the application of our formulation to random search, the formulation is also applicable other sampling-based search algorithms, such as reinforcement learning (RL) and Bayesian optimization (BO). Similar to NA-RS, when applying our formulation to RL or BO, we only need define the reward signal in RL or the objective function in BO as the aggregated performance 9 (f()) Other components in RL or BO remain unchanged.
4.2 NEIGHBORHOOD AWARE DIFFERENTIABLE SEARCH
We now present how to apply our formulation to differentiable NAS methods. The key in these methods (Liu et al., 2019 Xie et al. 2019 Chen et al. 2019) is make the objective f(a) differ- entiable with respect to the architecture a such that one can optimize a with gradient descent.
Similar to the case of random search, formulation changes the objective from f(a) to g (f()) With this change, the differentiability of g (f(N(a))) is not guaranteed. There- fore, propose differentiable neighborhood representation for M(a) and set the aggregation
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Neighbbrrhood-Awaae DARTS
Input: Number of steps T. Number of neighbors Rabe- Initial architecture a and weights w. for ( 1, ..,,...,7 do
Sample a batch of training data X and batch of validation data Xval- Sample Pabr neighboring architectures of a: M(a)..
Compute Va La' Cua(w,a')
on val update a by descending V. Eorenion Cul(waa) [Waa)
[N(a)] Compute Vw (W, a)) X update by descending V Wu (w,a). a).
end for Derive the final architecture based on the learned a.
function g(.) to be mean (g can also other differentiable functions). This makes g (f()(a))) differentiable and allows simply adopt prior gradient estimation techniques, e.g. the continuous relaxation in DARTS (Liu et al. (211)) or Gumbel-Softmax in SNAS (Xie et al. 2019). to derive the gradient of g (a))- Other parts in the original diffferentiable NAS methods remain the same.
Specifically, we augment DARTS (Luu et al. 2019) with our formulation and adopt the continuous relaxation in DARTS to estimate the gradient. Therefore, name method neighborhood DARTS (NA-DARTS). Note that our formulation is also applicable to other differentiable NAS methods, such as SNAS (Xie et al. 2019) and P-DARTS (Chen et al. 2019).
4.2.1 NEIGIBORRIOOD-AAWRR DARTS
We first briefly review DARTS and then introduce the formulation of our NA-DARTS.
DARTS. DARTS relaxes the discrete search space to be continuous so that the gradient of the vali- dation loss with respect to the architecture can be estimated, allowing optimizing with gradient descent. Concretely, a (1-) is relaxed from discrete one-hot vector to a continuous distribution,
and is parameterized as the output of the softmax function: ag (f.j) En ex
exp(e(
where is
the number of available operations and [ } is the set of continuous logits to be learned. DARTS formulates NAS as the following bilevel optimization problem:
min Lew (w" aa) s.t. w w*(a) (a) arg min (wain(, a),
(4)
where w denotes network weights, w" w²(a) (a) denotes the weights minimizing the training loss of archi- tecture Luran (w. a)) and (w, a.) are the training loss and validation loss of architecture a with weights w, respectively.
NA-DARTS. We augment DARTS with our neighborhood- formulation:
min g( Lva (a'),a') a' (a())) s.t. w (a') arg min Lurin a'),
(5)
where (a) is the neighborhood of architecture a and g(-) is an aggregation function.
An outline of the proposed NA-DARTS algorithm can be found in Algorithm 1 We first describe how to represent the neighboring architecture a' as a differentiable function of a and, then discuss the gradient estimation for specific choices of g(-).
4.2.2 DIFFERENTIARI NEIGHRORHOOD REPRESENTATION
When the one-hot constraint on is relaxed, the neighborhood contains an infinite number of neigh- boring architectures. We propose a method to sample finite number of architectures from the neighborhood. Importantly, method allows each sampled neighbor a' to be differentiable with respect to the reference architecture a.
We generate neighboring architectures of a by perturbing the operations associated with the edges in a. We randomly sample edges to be perturbed from the edge set E of a and leave the opera- tion choice for the remaining edges unchanged. This implies that the distance between and the neighboring architecture is at most thus as defined in Eq 3 a' falls into the neighborhood of a. Next, we present how represent a' as differentiable function of a.

---

Under review as a conference paper at ICLR 2021
Let edge (i.j) be edge to be perturbed. Let ((3)) ) be m-dim real-valued noise vector satisfying the following condition: lok [ - e(0 < E << 1) and ax (1.5) + 9k 2 for all k(1 & I m). e is
the threshold of the noise. We randomly sample noise vector o (1..)) and (((d)) is computed as:
ak (i.)
9 (i:5)
(3 0
[a=
(1-) (a + 9 (())
Repeating the process for each edge to be perturbed will result in neighboring architecture a', which is differentiable with respect to a. Different noise vectors are sampled for different edges. We term the representation of a' in Eq. Gas the additive representation of neighboring architectures.
With the additive representation, we can sample set of neighboring architectures of and the sampled architectures are differentiable with respect to a. In practice, we uniformly sample T'bre neighboring architectures from the neighborhood and always include a itself in the sampled set.
4.2.3
GRADIENT ESTIMATION
After sampling a finite set of neighboring architectures, we compute the validation loss of each individual architecture a', where we use the current network weights w as an approximation of w" (a'). Then we pass the of the validation losses the aggregation function g(-).
As discussed before, the aggregation function g(-) needs to be differentiable, which immediately rules out median. We choose mean over max due to superior empirical performance. We note that when using max, Eq. becomes minimax optimization problem and one can approximate the gradient of the objective using Danskin's Theorem (Danskin 1967). For completeness, we provide details of using max in the appendix.
5 EXPERIMENTAL RESULTS
5.1
NEIGHIBORIIOOD-AWARR RANDOM SEARCII
(Dong & Yang 2020). Same as the experimental setup in Sec, 3.3] we search on CIFAR-10 and evaluate on CIFAR-I0 (Krizhevsky et al., 2009). CIFAR- (Dong & Yangl (0220.. The number of search steps T in NA-RS is set to 100. We set the distance threshold to 1 and sample 10 neighbors (Arb 10) at each step. Please see the appendix for more details.
We validate NA-RS
100 (Krizhevsky et al. 2009), and ImageNet-16-
As shown in Table 2 NA-RS consistently outperform RS on all three datasets, which validates neighborhoodd-waree formulation. Notably, NA-RS outperforms RS by 1.48% CIFAR-100 and 1.58% 1eageNet-16-120., Note that the cell search space typically has a narrow performance range (Yang et al. 2020), the improvement brought by our NA-RS is non-trivial. We include the ablation study of Rbb and the aggregation function in NA-RS in the appendix.
5.2 NEIGHEORHOOD-AWARR DARTS
Following the experimental setup in DARTS (Liu et 2019), we search on CIFAR- 10 Krizhevsky
al. 2009) and evaluate on three datasets: CIFAR-I0 Krizhevsky al. 2009). CIFAR-
100 Krizhevsky et al. 2009) and ImageNet (Russakovsky et al. 2015). The performance on
Table 2: Test error of NA-RS and the standard random search (RS). NA-RS consistently outperforms RS on all three datasets under the same computational budget.
CIFAR-10
CIFAR- 100
ImageNet- 120
Random Search (RS)
6.39
0.32
29.81 0.44
56.30 +: 1.08
NA-RS (Ours)
6.20
0.35
28.33
1.22
54. 0.96
Table 3: Test error of NA-DARTS and DARTS on CIFAR-10, CIFAR-100 and ImageNet. Our NA-DARTS consistently outperforms DARTS on all three datasets.
Top-1 Test Error (%) CIFAR-100 100
Params (M)
Method
CIFAR-10
ImageNet
CIFAR
ImageNet
DARTS 1st (Liu et al.
2019
2.90 + 0.25
17.66 + 0.83
2.9
DARTS 2nd [Lu et 2019
2.70 0.08
17.72 0.61
26.7
2.9
4.7
NA-DARTS (Ours)
2.63 + 0.12
16.48 + 0.13
25.5
3.2
4.8
7

---

Under review as a conference paper at ICLR 2021
Table 4: Comparison with state-of-the-art NAS methods on CIFAR-IO and CIFAR-100. Our NA- DARTS achieves the lowest test eтror on CIFAR-100. As all the architectures are searched on CIFAR-10, this shows that architectures found by NA-DARTS generalize better.
Test Error (%)
Params (M)
Search Cost
Search Method
Method
CIFAR-10
CIFAR-100
(GPU days)
NASNet-A (Zoph et al.
2018
2.65
17.10*
3.3
1800
RL
AmoebaNet-A (Real
2019
2.84"
17.16"
3.2
3150
Evolution
PNAS Liu et al. 2018
2.95'
17.29*
3.2
225
SMBO
ENAS Pham et al. 2018
2.54"
17.18"
3.9
0.5
RL
SNAS Xie et al.
2019
2.85 + 0.02
18.25"
2.8
1.5
Gradient
P-DARTS (C Chen al. 2019
2.50
16.55
3.4
0.3
Gradient
PC-DARTS (Xu et al. 20200
2.57 + 0.07
16.74"
3.6
0.1
Gradient
DARTS+ (Liang al.. 2019
2.72'
16.85
4.3
0.6
Gradient
DARTS 1st (Liu et al.
2019
2.90 = 0.25
17.66 + 0.83
2.9
0.3
Gradient
DARTS 2nd (Liu
2019
2.70 = 0.08
17.72
+ 0.61
2.9
1.0
Gradient
NA-DARTS (Ours)
2.63 = 0.12
16.48
+ 0.13
3.2
Gradient
train the reported architecture following the training setup DARTS (Liu al. 2019).
Table 5: Comparison with state-of-the-art NAS methods on ImageNet. Our NA-DARTS obtains the second lowest test error on ImageNet. We expect further improvement since our contribution orthogonal to other extensions of DARTS (e.g.. P-DARTS, PC-DARTS and DARTS+).
Test Ervor (%)
Params (M)
+X (M)
Test Error (%)
Params (M)
+X
Method
Top-1
Top-5
Method
Top-1
Top-5
(M)
DARIS LLu et al. 2019
26.7
8.7
4.7
574
AmoebaNettA Real et
2019
27.0
8.9
5.0
584
P-DARTS hen et 2019
25.3
8.1
4.9
NASNet-A (Zopa et al. 2018
26.0
8.1
5.3
PC-DARTS Xu
2020
25.7
8.3
586
ENAS
(Pham
2013
26.1
8.6
5.2
576
DARIS+ Lianng el all
2019
26.4
8.5
5.0
586
PNAS
Lau et al. 2018
25.8
8.1
5.1
588
NA-DARTS (Oui)
25.5
SNAS
et all 2019
27.3
9.2
We train the reported architecture following training setup DARTS
Liu
2019
CIFAR-100 and ImageNet are more important, which reflects how well the found architecture can generalize to new datasets. For our NA-DARTS, we sample 10 neighboring architectures at each step, i.e. Fbhr 10. Complete experimmntl details and ablation results are included in the appendix.
We first compare our NA-DARTS with DARTS. This comparison directly verifies the effectiveness of our neighborhood-aware formulation. As shown in Table NA-DARTS consistently outperforms DARTS on all three datasets. Notably, NA-DARTS outperforms DARTS by 1.18% on CIFAR-100 and 1.2% on ImageNet. Note that the cell search space used in DARTS has narrow performance range Yangg et al. 2020). For example, the top-1 error on CIFAR- 100 mostly fall around 17%. So the performance gap between our NA-DARTS and DARTS is non-trivial. We also compare NA- DARTS and DARTS using different search space in the appendix and observe bigger gap.
NA-DARTS also outperforms or performs on par with other state- state-of-the-ae of-the-art NAS methods (Table & 5.) NA-DARTS obtains the lowest test error CIFAR- 100 and the second lowest on ImageNet among state-of-the-an NAS methods. Note that P-DARTS, PC-DARTS and DARTS+ are all exten- sions of DARTS and the neighborhood improve DARTS, e.g., gradually increasing search depth in P-DARTS and the partial-channel con- nection idea in PC-DARTS, can all be combined with method for better performance. Therefore, our improvement is complementary to theirs in reference to DARTS. We provide further results of applying our formulation to PC-DARTS in the appendix.
formulation is also applicable them. Their ideas to
CONCLUSIONS
To achieve better generalization, we propose a novel neighborhood-aware NAS formulation, based on the assumption that flat-minima architectures generalize better than sharp ones. Our formula- tion provides a new perspective for NAS that one should use the aggregated performance over the neighboorhood as the criterion to select optimal architectures. We also demonstrate a principled way to apply our formulation existing search algorithms and propose two practical search algorithms NA-RS and NA-DARTS. Extensive experiments on CIFAR-10, CIFAR-100 and ImageNet validate the flat minima assumption, and demonstrate the significance of formulation and algorithms.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architec- tures using reinforcement learning. In ICLR, 2017.
Gabriel M. Bender, Pieter jan Kindermans, Barret Zoph. Vijay Vasudevan, and Quoe Le. Under- standing and simplifying one-shot architecture search. In ICML., 2018.
Shengcao Cao, Xiaofang Wang, and Kris M. Kitani. Learnable embedding space for efficient neural architecture compression. In ICLR, 2019.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In ICLR, 2017.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In ICCV, 2019.
John M Danskin. Springer, 1967.
The theory of max-min and its application to weapons allocation problems.
Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv: 045552, 2017.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. ICML, 2017.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In ICLR, 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. JMLR, 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 1997.
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. In NeurIPS, 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In ICLR, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In NeurlPS, 2018.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In UAI, 2019.
Mengtian Li, Ersin Yumer, and Deva Ramanan. Budgeted training: Rethinking deep neural network training under resource constraints. In ICLR, 2020.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping. arXiv 2019.
preprint
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.

---

Under review as a conference paper at ICLR 2021
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurIPS, 2019.
Hieu Pham, Melody Guan, Barret Zoph. Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In ICML, 2018.
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc Le, and Alexey Kurakin. Large-scate scale evolution of image classifiers. In JCML, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Scan Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenct large scale visual recognition challenge. IJCV, 2015.
Lingxi Xie and Alan Yuille. Genetic enn. In ICCV, 2017.
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. Po-darts: Partial channel connections for memory-effictee architecture search. In ICLR, 2020.
Antoine Yang, Pedro M. Esperança, and Fabio M. Carlucci. Nas evaluation frustratingly hard, In ICLR, 2020.
Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian-based analysis of large batch training and robustness to adversaries. In NeurIPS, 2018.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In ICLR, 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu. Practical block-wise neural network architecture generation. In CVPR, 2018.
Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. ICLR, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In CVPR, 2018.
A GENERALIZATION TEST ON A NEW SEARCH SPACE
Zela al. 2020 finds that on a wide range of search spaces, while DARTS (Liu al. 2019 can successfully minimizes the validation loss during search, the found architectures are usually degen- erated and generalize poorly to the test setting. To further validate our NA-DARTS, we conduct experiments on the search space suggested by Zela et al. (2020) and show that in this new search space, NA-DARTS can still find architectures that generalize much better than DARTS.
The new search space is subset of the original DARTS search space. The new search space is exactly the same as the original search space, except that only considers three candidate operations. including 3 3 separable convolution, skip connection, and the operation. Following Zela al. 2020), we refer to the new search space as 'S3 search space'.
We search architcctures from the S3 search space CIFAR-10 using DARTS (Liu et al. 2019), DARTS-ES (Zela et al., 2020) or our NA-DARTS, and then evaluate the found architecture on both CIFAR-10 and CIFAR-100. DARTS-ES is DARTS with an early stopping criterion based
10

---

Under review as a conference paper at ICLR 2021
Table 6: Test error of architectures found from the S3 search space on CIFAR-10 and CIFAR-
100. Top: our NA-DARTS significantly outperforms DARTS on both CIFAR-10 and CIFAR-100. Bottom: applying our formulation to PC-DARTS yields further improvement. Our NA-PC-DARTS outperforms PC-DARTS by 0.72% on CIFAR-100.
CIFAR-10
CIFAR-100
DARTS LLu
2019
4.13 + 0.98
22.49 2.62
DARTS-FR ES (Zela et al. 2020
3.71 + 1.14
NA-DARTS (Ours)
2.97 + 0.18
18.86 + 0.49
PC-DARTS (Xu et al. NA-PC-DARTS (Ours)
2020
2.66 + 0.14
17.38 + 0.45
2.69 = 0.08
16. + 0.39
on the dominant eigenvalue of the Hessian of the validation loss. We summarize the performance of DARTS, DARTS-ES and NA-DARTS in the top half in T We see that our NA-DARTS outper- forms both DARTS and DARTS-ES on CIFAR-10. Notably, NA-DARTS outperforms DARTS by 3.63% on CIFAR-100, which demonstrates that architectures found by NA-DARTS generalize much better than those found by DARTS. The performance of DARTS-EE on CIFAR-10 is from Zela et al. (2020). We do not report the test eπrо of DARTS-ES CIFAR- 100 becauses architectures found by DARTS-ES on CIFAR-10 are unavailable to us.
Zrom/Zela
In the main text, mention that our contribution is orthogonal to other extensions of DARTS CCen jet al.] 2019; Xu et al.] (020) and we expect better performance after applying our formulation to them. We propose NA-PC-DARTS by applying our neighborhoodd-wware formulation to PC-
DARTS (Xu et al. 2020). and obtain further improvement. We evaluate PC-DARTS and our NA- PC-DARTS on the S3 search space and report the results in the bottom half in Table
We notice that NA-PC-DARTS performs similarly to PC-DARTS on CIFAR-10. We would like to emphasize that the DARTS search space (a superset of the S3 search space) has narrow perfor- mance range as verified in Yang et al. (2020) and the test error of most NAS methods on CIFAR-10 are within [2.%%, 3.0%]. So focus more on the performance on CIFAR-100 Our NA-PC-DART'S outperforms PC-DARTS by 0.72% on CIFAR-106 Note that all the architectures are searched on CIFAR- 10, this shows that architectures found by our NA-PC-DARTS generalize better than those found by PC-DARTS. We obtain further improvement after applying our formulation to PC-DARTS.
B AGGREGATION FUNCTION
B. MORE CHOICES FOR AGGREGATION FUNCTION
Our formulation aims to identify flat minima in the search space based on the aggregated perfor- mance (f(()))) over the neighborhood. The aggregation function g(.) needs to be properly set such that minimzing g (f()(a))) results in architecture that is local minimum and at the same time has a flat neighborhood.
The flatness of the neighborhood of is determined by how much the performance (e.g., valida- tion loss) of its neighboring architectures varies compared to a itself. Intuitively, when a is a flat minimum, its neighboring architectures should perform similarly to However, when a is sharp minimum, the loss of architectures around a increases drastically compared to a. Although the formal definition of flatness sharpness of local minimum is not exactly the same in previous work (Hochreiter & Schmidhuberi 1997 Chaudhari et al. 2017 Keskar et al. 2017 Dinh et al.) 2017 Yao al. 2018), they all share this intuition.
We discuss possible choices for the aggregation function g()):
mean, median or max.
The architectures around sharp minimum tend to high much higher loss compared to this minimum. Therefore, the mean validation loss of architectures around flat minimum is expected to be lower than those around a sharp minimum. Minimizing mean (a)) encourages the convergence architecture whose neighbors in A N(() all have low

---

Under review as a conference paper at ICLR 2021
loss, which implies that is a flat minima. This makes mean valid choice. For similar reason, median and max are also valid choices.
Setting g(.) as mean or max also aligns well with previous work on flat minima. Chaudhari ett al. (2017) propose an objective function for training neural networks so that flat minima are preferred during optimization. Their objective can be interpreted as weighted average of the (transformed) function values of data points around the local minima, which inspires to consider mean function value that can be attained in the neighborhood of a local minimum to characterize how sharp the minimum is, which leads to set g()) max. Variance.
of the choices for g(-). Keskar et al. (2017) use the largest
For an architecture a, we can measure its flatness with the variance (standard deviation) of the performance of its neighbors in (aa). Let (a)()))) denote the standard deviation the performance (e.g., validation loss) of architectures in (ax). But simply minimizing a (a)) can only result in a is local minimum (e.g., have low validation loss). So we propose the following variance-bain based aggregation function g (J ([((aa))
with flat neighborhood, but cannot guarantee that
f(a) + (J((((())) that takes both the performance of a and the flatness of its neighborhood into account, where À is hyper- parameter to balance the performance f(a) and the flatness o (((()))))
B.2 AGGREGATION FUNCTION IN DIFFERENTIABLA ARCHITECTURE SEARCH
When applying our formulation to differentiable NAS methods, g(-) needs to differentiable, which immediately rules out median. Our default choice is mean and provide an outline of NA-DARTS using mean in the main text.
Both mean and the variance-based aggregation function are differentiable. We prefer mean because it requires fewer GPU memory. Theoretically, when computing Vag (f(N(a))), we need to keep all architectures in (M(a) in GPU. But when g(.) mean, we can compute V. vff(aa) separately for each neighbor a' E (a).. Since PyTorch (Paszke et al. (209)) automatically accumulates the gradient in multiple backward passes, computing VaJ(a') separately is equivalent as computing Va mean (f(((o))) Therefore, when using mean, we only need to keep one architecture in GPU. This requires much fewer GPU memory than the variance-basee brssacce-basdddee aggregation function.
We prefer mean over max due to its superior empirical performance. When using max, Eq. 5 be- comes a minimax optimization problem and one can approximate the gradient of the objective using Danskin's Theorem (Danskin 1967). Same as mean, max also only needs to keep one architecture in GPU (see following text for more details).
Algorithm Neighborhood
DARTS
Input: Number of steps T' Number of neighbors Tobe. Initial architecture a and weights w. for = 1, 1,2..... T.....To. do Sample a batch of training data Xusin and a batch of validation data X
Sample Thnbr neighboring architectures of or: N())).
if (()) == max then
Compute ā arg (axa' (w, a') on X
Compute V Cva(wu (w. @) on Xval update a by descending V (w. (0, ā).
else if g(-) = mean then
Compute V. Eafe faa(waa)) [N(a)]
on X update a by descending V. EaTeNtos faalmaa)) (N(a))
end if Compute Veriin (w, a) on Xusani update w by descending V Cirain (w, (w,a). end for
Derive the final architecture based on the learned a.
B.2.1 USING max IN NA-DARTS
For completeness, we describe details of using max in NA-DARTS. After setting g(.) as max, Eq. 5 becomes minimax optimization. According to Danskin's Theorem (Danskin 1967),
12

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Neighborrhood-Awaare Random Search
Input: Number of steps T. Number of neighbors Rabe- for ( = 1,2...... T do
Randomly sample architecture from A: Sample nabr neighboring architectures of a: M(a).
Train the Rabr architectures and compute (f (f(V)))))
Let a = a if (f()()))) < <I(V((( end for Return the optimal architecture a".
can approximate the gradient Vo (a (a), with V Ca (ā), a), where is the maximizer of the inner maximization problem maxa'EN(a) Laa(w" (a'),a'). In practice, w" (a') is approximated by the current network weights w. To compute the maximizer a, we simply compute the validation loss each sampled neighboring architecture and choose the maximum one. We provide outline of NA-DARTS in Algorithm 2] where include steps for both cases (g(-) = max or g(-) = mcan). As can seen from Algorithm 2 when using max, we only need to keep one architecture (α) in GPU during the gradient computation.
Solving the inner maximization problem ee(a)) Lval (a'), a') is the process of finding the worst-performing neighbor of in its neighborhood. Sampling neighbors with the additive repre- sentation of neighbors (Eq. 6) might not always result in a neighbor a' that performs worse than a. So, we develop the following multiplicative representation of neighboring architectures. The multiplicative representation allows us to sample a' by changing a subset of operations in a to the zero operation or skip connection such that a' has a higher probability to perform worse than a.
Let edge (i.j) be an edge to be perturbed and p(i.)) be m-dim one-hot vector with ri (f.5) = 1 and (i.)) = 0(1 < S m,k k # 1). We restrict to be either the index of the zero operation or skip rk
connection. With the one-hot vector ((is), a(iij) is computed as:
(1.5) (6.) Tk Okk
(i.))
ag
Σ Σr a 6.
(15)
Under the multiplicative representation, (i.5) has the same value as ((-)), which indicates that the edge (i,j) after perturbation chooses either the zero operation or skip connection. We empirically observe that max works better with the multiplicative representation than additive representation.
C ASSUMPTION JUSTIFICATION
C.I EXPERIMENTAL SETUP
We describe the detailed setup our assumption justification experiments in Sec. 3.3. NAS-Bence 201 (Dong & Yang 2020) provides a simulated environment for NAS experiments by conducting thorough evaluation of all the candidate architectures (cells) in pre-defined cell search space on three datasets: CIFAR-10 (Krizhessyy et al. 2009) CIFAR- 100 (Krizhevsky et al. 2009), and ImageNet-16-115 16-120 (Dong & Yang. (020)). It contains the validation error (accuracy) all the can- didate architectures on CIFAR-10 10 after every training epoch, and the final test error CIFAR-10, CIFAR- 100, and ImageNet- 16-120. ImageNet- 20 a subset and downsampled version of Im- ageNet (Russakovsky et al. 2015) and contains about 158K images divided into 120 classes.
In our experiments, we set the distance threshold to 1, so each architecture in the search space has 25 neighbors including itself. We search on CIFAR-10 and evaluate the found architectures on all three datasets, i.e., f(a) is defined as the validation error on CIFAR- 10. It is common in NAS to early stopping budgeted training during search (Elsken et al. 2019 Li ct al. 2020). So, we use the CIFAR- 10- Validation error after the th epoch in the experiments, un- less otherwise stated. Results for other epochs (e.g., 30th t0th t2 lead to the same conclusion.
13

---

Under review as a conference paper at ICLR 2021
C.2 FLAT MINIMA GENERALIZE BETTER
We provide results for other epochs to show that flat minima in the architecture space generalize better than sharp minima. Specifically, we conduct the same experiments as Sec. 3.3.1 (Table the main text) with the CIFAR- 10- Validation enror after the 30th, 60 or 120 epoch. As shown in Table 7 results for all epochs (30th 60th, 90th 120th) demonstrate the same pattern: the average validation error on CIFAR-10 of flat minima and sharp minima are similar; however, the average test error of flat minima is consistently lower than sharp minima on all three datasets, especially on CIFAR-100 and ImageNet-16-120.
C.3 AGGREGATED PERFORMANCE GIVES BETTER RANKING OF ARCHITECTURES
We show that our criterion g (f(N(a))) ranks architectures more accurately than the standard crite- rion f(a). To do that, we randomly sample 100 architectures from NAS-Bench-201 and rank these architectures according to our criterion g (f(N())) or the standard criterion f(a), where f(-) is the validation eтror on CIFAR-10. Following Yu et al. (2020), we evaluate the estimated ranking with the Kendall's Tau metric (the higher the better), which measures the correlation between the estimated ranking and ground truth ranking of architectures. The ground truth obtained by sort- ing these architectures based on their test error. As the ground truth is specific to each dataset, we evaluate the estimated ranking on the three datasets separately.
We repeat the experiments for 10 times and report the mean and standard deviation of the Kendall's Tau value. Table (main text) shows the ranking estimation results when g(-) = mean. We provide the results for all the aggregation functions in Table 8 For the variance- aggregation function, we set À to 1.0. All aggregation functions except max result in an more accurate ranking estimation of architectures than the standard criterion fa).
C.4 AGGREGATED PERFORMANCE FINDS FLAT MINIMA
We conduct quantitative analysis to show that optimizing the proposed criterion, i..e, the aggre- gated performance over the neighborhood, finds flat minima. We select 100 architectures from NAS-Bench-201 with the lowest validation error (baseline criterion) on CIFAR-10 10, and another 100 architectures with the lowest aggregated validation error (proposed criterion).
We measure the flatness of an architecture using neighborhood variance, where smaller variance indicates flatter neighborhood. We summarize the neighborhood variance and test error of the found architectures in Table We observe that optimizing the mean validation error ("Ours mcan') ') can successfully help us find flat minima, as the found architectures have a much smaller neighborhood variance than those found by the baseline criterion, and also achieve lower classification error all three datasets.
We also notice that when g(.) max, the found architectures are not flat minima. Although these architectures have a flat neighborhood (low neighborhood variance), their classification performance worse than architectures found by the baseline criterion. We think this is because when using max, the objective (a))(a)) only considers the flatness of the neighborhood, but fails to characterize how well the architecture a performs.
D NA-RS
Experimental setup. An outline of NA-RS is provided Algorithm 3 Same as the setup in the as- sumption justification experiments, we search on CIFAR-10 and evaluate on CIFAR-10 10 (Krizhevsyy al. 2009), CIFAR-100 (Krizheskyy et al. 2009), and ImageNet- 16- 1-120 (Dong & Yang 2020). The number of search steps T in NA-RS is set to 100. For fair comparison, the standard random search (baseline; denoted as 'RS') is run for T' naar steps, so that RS and NA-RS train and evaluate the same number of architectures. We set the distance threshold d to 1, the neighborhood contains 25 architectures including the reference architecture itself. We set naarr to 10 unless otherwise stated.
Ablation study. We provide ablation study of the aggregation function in NA-RS in Table I0 and an ablation study of 7hhr in Table [T]] We see from Table I0 that mean and median achieve the best performance among all the choices for g()). max performs the worst, which is consistent
14

---

Under review as a conference paper at ICLR 2021
Table 7: Average error of flat-minima architectures and sharp-minima architectures. "CIFAR-IO- Validation" refers to the average validation error on CIFAR-10 10 used in search. CIFAR-IO, CIFAR- 100 and ImageNet- 1e-ett-1-1111 16-120 refer the average test error on each dataset. Flat minima and sharp minima obtain similar validation error CIFAR-10. However, flat minima consistently achieves lower test error than sharp minima on all three datasets.
(a) ((a) CIFAR-IO Validation error after the 30th epoch.
CIFAR-10 10- Validation
CIFAR-10
CIFAR-100
ImageNet-166120)
Flat minima
18.39
6.33
29.15
55.52
Sharp minima
18.45
6.67
30.10
56.18
(b) [(a) = CIFAR-IARR -O- Validation error after the 60 epoch.
CIFAR--O-Validation
CIFAR-10
CIFAR- 100
1mageNet-16-120
Flat minima
16.15
6.28
29.15
55.51
Sharp minima
16.43
6.91
30.56
57.31
(c) [(a) = CIFAR-IO- Validation error the 90 epoch.
CIFAR--O-Validattin
CIFAR-10
CIFAR-100
ImageNet-16-120
Flat minima
14.55
6.23
28.90
55.17
Sharp minima
14.57
6.66
30.00
56.41
(d) f(ax) CIFAR-I0 Validation error after the 120 epoch.
CIFAR-10- CIFAR-IO-Validation
CIFAR-10
CIFAR-100 100
ImageNeet-16112 16-110
Flat minima
12.67
6.13
28.59
55.11
Sharp minima
12.81
6.33
29.28
55.53
Table 8: Kendall's Tau (rank correlation) obtained by the standard criterion f(a:) (baseline) and our criterion g (f(()))) with different choices of 9(-).
CIFAR-10
CIFAR-100
Baseline
0.66 0.03
0.66 = 0.02
0.64 0.03
Ours mean
0.76 0.03
0.77 + 0.03
0.74 + 0.03
Ours median
0.72 + 0.03
0.72 = 0.03
0.69 = 0.03
Ours max
0.53 0.05
0.54 = 0.05
0.56 = 0.05
Ours Variance
0.72 + 0.02
0.73 + 0.03
0.71 + 0.02
Table 9: Neighborhood variance and test error of architectures found by by the standard criterion f(a) (baseline) and our criterion g (f(N(a))) with different choices of g(-). Architectures found by the validation error ("Ours mean') have much smaller neighborhood variance than those found by the baseline criterion, and also achieve lower classification error on all three datasets.
Neighbor- Var
CIFAR-10
CIFAR-100
ImageNet-166 16-120
Baseline
5.58
6.45
29.45
55.79
Ours mean
2.71
6.09
28.32
54.75
Ours median
4.05
6.21
28.74
55.08
Ours max
1.83
6.66
29.82
56.31
Ours Variance
2.47
6.35
29.06
55.52
with the conclusion in Table 8
As shown in Table 11 performance obtained by 74mbr 10 is close
to nhhrr 25, which indicates that sampling a subset of neighbors is a good approximation for the entire neighborhood.
15

---

Under review as a conference paper at ICLR 2021
Table 10: Ablation study on the aggregation function in NA-RS, mean and median yield the lower test error among all the choices for g(-).
CIFAR-10
CIFAR-100
ImageNet-16-120
NA-RS mcan
6.39 + 0.71
28.68 + 1.75
55.02 + 1.71
NA-RS- median
6.20 0.35
28.33 + 1.22
54.72 + 0.96
NA-RS- max
6.73 + 0.71
29.70 + 1.61
56.96 + 2.09
NA-RS Variance
6.65 = 0.97
29.06 + 1.97
55.48 + 2.41
Table 11: Ablation study on nhhr in NA-RS. Sampling a subset of neighbors (Ninbe = 10) a good approximation for the entire neighborhood (Aahr 25).
CIFAR-10 10
CIFAR-100
ImageNeet1661221
NA-RS- mean
Tabr 10
6.39 = 0.71
28.68 + 1.75
55.02 = 1.71
Tabr = 25
6.24 = 0.39
28.24 + 1.25
54.74 1.73
NA-RS median
Trabe 10
6.20 + 0.35
28.33 + 1.22
54.72 + 0.96
Taar 25
6.18 + 0.38
28.20 + 1.27
54.40 + 0.98
E NA-DARTS
E.I EXPERIMENTAL SETUP
Following DARTS Liu al. 2019). search CIFAR- (Krizheskyy al. 2009) and evaluate on CIFAR-10 10 Krizhevsky et al. 2009). CIFAR-100 (Krizevsky et al. (2099) and ImageNet (Rus- sakovsky et
search space, 2015). We use exactly the same setup as DARTS such as the learning rate and weight decay factor, and other exper- imental details. We split the training images CIFAR-10 into two subsets of equal size, which are used as the training and validation images during search. We construct a network of 8 cells with an initial channel number as and train the network for 50 epochs to learn a.
al. (2019), including the cell
After the search is done, we derive the final architecture from the learned a using exactly the same procedure as DARTS. When evaluating the found architecture on CIFAR-10 10 and CIFAR-100, 100, we build network of 20 cells and train it for 600 epochs with batch size 96 and cutout VDess & Taylor 2017). For our NA-DARTS, We set the initial number of channels the network such that has similar network size with DRATS and contains around 3M parameters.
When evaluating on ImageNet, we build a network of 14 cells. Following DARTS, the network trained for 250 epochs with batch size 128. We set the initial number of channels such that the number of multiply-add operations in the network fewer than 600M when the input is 224 x 224. Some NAS methods use different training setup train the found architecture ImageNet. For example, DARTS+ (Liang et al.) 2019) trains for 800 epochs and P-DARTS (Chen et al. 2019) uses large batch size 1024 (need V100 GPUs, infeasible us). For fair comparison, we retrain the found architecture reported by the authors in their paper using the same training setup as DARTS.
For our NA-DARTS, we sample subset of 10 neighbors in each step, i.e., Aahr 10. The distance threshold d for neighborhood can be interpreted as the number of edges to be perturbed. As each cell in the DARTS search space has 14 edges, we set d 6. The noise threshold in the additive representation is set to 0.1. All experiments are performed on NVIDIA GeForce RTX 2080 Ti GPU.
E.2 ABLATION STUDY
Aggregation function. We report the performance of NA-DARTS when using mean or max as the aggregation function in Table 12a We observe that mean outperforms max, which is consistent with the conclusion in Table 8 We also notice that mean consumes a longer search time than max.
This is because when using mean, need to back-propagate through every sampled neighboring
16

---

Under review as a conference paper at ICLR 2021
architecture a', while only need to back pack-propagaee through neighboring architecture when using max.
Distance threshold. We study the impact of the distance threshold of d in Table 12b where observe d = 6 achieves the best performance and d = 4 performs similarly with d = 6. Recall that the distance threshold d can be interpreted the DARTS search space has 14 edges. We empirically find that when d becomes larger that 6, the neighborhood becomes too large and the performance drops.
the number of edges to be perturbed and the cell in
Table 12: Ablation study of NA-DARTS.
(a) Impact of aggregation function.
Test Error (%)
Param (M)
Search Cost (GPU days)
CIFAR-10
(IFAR-100
max
2.80 + 0.10
16.89 + 0.31
3.1
0.5
mean
2.63 = 0.12
16.48 + 0.13
3.2
1.1
(b) Impact of d.
Test Error (%)
Param
CIFAR-10
CIFAR-100
(M)
2
2.62 + 0.08
16.90 + 0.45
3.2
= 4
2.65 + 0.19
16.56 + 0.36
3.1
2.63
+ 0.12
16.48 0.13
3.2
F LOSS LANDSCAPE VISUALIZATION
To qualitatively examine whether our NA-DARTS has found flat minima, we plot the loss land- scape of DARTS and NA-DARTS with the visualization strategy from et (2018).. Let a denote the architecture found by DARTS or NA-DARTS. We compute the Hcssian of the validation loss with respect to and vo and V1. which are the eigenvectors corresponding to the two largest eigen- values of the Hessian matrix. Then we visualize the validation loss of the neighbors of a over the plane spanned by to and V1. Specifically, Apeeificallyy we compute the validation loss of the architecture a + Ag + Vg where Ay and A are uniformly sampled from [-1.0, 1.0]. The loss values are visualized by the contour plots in Figure 2 We observe that the curvature of NA-DARTS at (0, 0) (the found architecture a:) is much flaterr than that of DARTS.
We provide details of the neighboring architecture a' the plus sign (+) with the additive representation. Recall that a contains a set of variables repre- senting the operation choice for each edge (i.j): a fa (i.i)) The eigenvectors Up and vi have and then can be represented vo ( and e1 (o( Let g(is)) = Aano (2.5) + \1r (6.5) (H.1)) then computed using the additive representation in Eq.
Ao X ti, where overload
the same dimension
(i.5)
(b.f) Da (a.0a)) + ). The eigenvectors vo and U1 normalized so that the scale of the
a (3.2)) (1.1) +0 (3.9
(a
noise vector ((+))) is controlled only by An and A₁. We use the weights of a obtained in the search as approximation for the weights of the neighbors a'.
G CELL VISUALIZATION
We visualize the normal cell and reduction cell found by DARTS and our NA-DARTS in Figure We observe that the normal cell found by our method NA-DARTS tend to be deeper than that found found by DARTS. Normal cells found by our NA-DARTE from different runs have a depth of at most of the time, while normal cells found by DARTS mostly have a depth of or 2. We also observe that the normal cell found by NA-DART'S contains more 5 x convolution operations. Both of the reduction cells found by DARTS and NA-DARTS contain very few convolution operations. Most operations in the reduction cell do not have parameters, e,g. pooling and skip-connection.
17

---

Under review as a conference paper at ICLR 2021
Validation Loss
Validation Loss
0.3
0.0
0.25
075
0.20
0.00
100
-0.75
-250
-015
0.00
5.25
2.0
0.75
1.02
-1.0
-075
-133
-223
3.0
0.25
1.52
0.75
3.00
Ag
As
(a) DARTS (standard formulation min ((a)).
Validation Loss
Validation Loss
1.50
1.00
0.75
0.75
0.0
-075
1.00
100
-0.15
-350
-0
0.00
0.28
2.02
-1.0
-1.0
-2.23
2.00
1.32 3.50
Ag
Ag
(b) NA-DARTS (neighborhoood-wware formulation min (f((()))))
Figure 2: Loss landscape visualization of the found architecture. The plots in Figure (Fig-
ure 26 are generated from two independent runs of DARTS (NA-DARTS). The left plot in Figure 2a and Figure 2b are the same as the plots Figure | in the main text. For the architecture found by DARTS (Figure 2ap. we observe that the loss of its neighbors increase drastically as the magnitude of Ån or A increases. However,
the architecture found by our NA-DARTS (Figure 2b the loss of its neighbors increases much slower. This shows that the architecture found by our NA-DARTS a much flatter minimum than that found by DARTS.
Eep 3xd
20A pool 3d
App comed
tep conv
mec peot.
conv 3et
Jlip conat
[k-2]
zpp cons
3c1
poo 3c
(a) DARTS normal cell (left) and reduction cell (right).
30-22
(b) NA-DARTS normal cell (left) and reduction cell (right).
Figure Cell Visualization.
18


Reviews:
[{"review_id": "tdO3MKS69ph", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Inspired by the concept that ``flat minima generalize better than sharp minima\", this paper proposes to search the flat-minima architecture by considering the performance over the neighborhood architectures. A random search and differentiable search method based on the neighborhood principle are proposed, which achieve comparable results with SOTA NAS methods. \n\nConcrete comments\n1. The biggest concern lies in the main idea of the neighborhood-aware search formulation. It is known in many previous methods that the flat minima of the loss function of neural network training generalize better. This conclusion is also extended to the eigenspectrum of the Hessian of the validation loss with respect to the architectural parameters in [1]. However, this paper hypothesizes that similar architectures with similar performance point to a flat solution. How it can be proven that nearby architectures are located in neighborhood in the loss space should be clarified. This is of critical importance to support the main concept of the paper.\n2. The proposed method is not so reasonable. The distance between architectures is defined as Eq. (2). However, many cases may fail with Eq. (2). For example, a 3x3 separable convolution is nearer to a 5x5 separable convolution, but further from the identity operation, which cannot be handled with Eq. (2). Moreover, the final operation is determined with the highest probability. [0.05, 0.6, 0.35] and [0.35, 0.6, 0.05] represent the same architecture, but different in Eq. (2).\n3. Experimental results are not so convincing. \n  - In Tab. 1 and 2, only test errors are reported but not Params or FLOPs. It is not clear whether advantages of the method actually exist. Normally, models should be compared with similar sizes.\n  - The proposed method does not show evident advantages over others, e.g., worse or similar compared with PC-DARTS but taking much more cost, 10x than PC-DARTS.\n  - The experiments are based on the DARTS-like search space. However this kind of search spaces hold high latency due to the complicated topology. What about the widely used MobileNet block-based search space?\n4. The novelty is somewhat limited. As the flat solution has been explored in [1], the main contribution seems to be the newly defined loss function ensemble with similar architectures. \n\n[1] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cXLzcqsESLS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a searching framework of neural architectures search by modifying the objective function to optimize the aggregated performance over the neighborhood of an architecture. From the observation that flat-minima architecture $\\alpha$ generalizes better than sharp-minima architecture (Zela et al. (ICLR2020), the author proposes the objective function considering the neighborhood to enforce the flat minima. The author supports their method by providing ablation studies and architecture performances from CIFAR-10/100, ImageNet, and NAS-BENCH-201.\n\nStrength\n1. Their objective function can easily be extended to existing NAS methods including Random Search and Gradient-Based methods. \n2. The authors support their methods with various datasets such as CIFAR-10/100 and ImageNet\n3. The paper supports their assumption with various empirical experiments and ablation studies. \n\nWeakness\n1.  The experiment results are incremental improvements (or par) to the existing NAS algorithms. By listing the recently published NAS literature on CIFAR-10: P-DARTs: 2.50%, DATA: 2.59%, SGAS: 2.66%, PC-DARTs: 2.57%, RandomNAS-NSAS: 2.64%. \n2. Few experiments on NAS Benchmark. The experiments don't include NAS-Bench-201 (a popular benchmark for NAS) and small experiments with NAS-Bench-1SHOT1 only comparing with DARTs, PC-DARTs. And PC-DARTs result is better than NA-PC-DARTs according to Table 6. \n\n\nQuestion\n1. How do you select the number of neighbors? In the DARTs setup, the normal/reduce cell would have $(2+3+4+5)*7*2=196$. The possible neighboring architectures from a given subnetwork even with hamming distance 1 may be much larger than 10. Can you visualize the loss landscape based on various $n_{nbs}$?\n2. Have you tried to verify your algorithm for NA-DARTs on NAS-Bench-201 which is the popular benchmark in recent NAS literature?\n3. The reproduced ImageNet test error results on PC-DARTs and P-DARTs are higher than the reported test results. The reported test results on PC-DARTs outperforms the NA-DARTs result. Is the resulting discrepancy related to hyperparameter tuning? Can you clarify this? \n\nOverall, this paper proposes a neighborhood aware objective function that can be adopted in the existing NAS search. Despite the paper well written, the performance of their methodology is incremental improvements (or par) among various existing NAS algorithms. I would recommend a marginally below acceptance threshold for now but may change the decision based on the rebuttal. \n\nReference:\n1. Xu, Y et al. (2019, September). PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search. ICLR2020\n2. Chen, X et al. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. ICCV2019\n3. Chang, J et al. DATA: Differentiable ArchiTecture Approximation. Neurips2019\n4. Li, G et al. SGAS: Sequential Greedy Architecture Search. CVPR2020\n5. Zhang, M et al. Overcoming Multi-Model Forgetting in One-Shot NAS with Diversity Maximization. CVPR2020\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "aSWQy9FKJcC", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a neighbor-aware method in the neural architecture search (NAS). The paper states that by optimizing a neighbor of the neural network, it can search the result in a flat-minima, which is more stable than the sharp minima. The experiment results in further support that the proposed NA-RS and NA-DARTS outperform the current SOTA in various tasks.\n\nOverall, I think the paper raises an interesting opinion, which stresses that during the NAS process, a stable flat-minima has a better generalization ability. The definition of the neighbor of the neural architecture is also interesting. Below are some detailed points of my opinion about this paper.\n\nPros:\n1. The paper compares with a lot of NAS methods and outperforms most of them.\n2. Stabilize the search result can reach a better performance seems reasonable for me.\n3. The ablation study in the appendix further shows the performance under different aggregate functions and distances, which makes the experiment more convincing.\n\nCons:\n1. From the paper's statement, sample-based NAS is easier to define the neighbor than the gradient-based one. However, from the empirical result, the sample-based NAS result is relatively weak compared with the differential based. DARTS also provides the result of the random sampling on their search space. It is interesting to see whether NA-RS can outperform the naive random sampling and even catch up with some other NAS method in DARTS's setting and search space. Currently, I think only test the sample-based method on NAS-Bench-201 is a little bit toy.\n\n2. PC-DARTS has reported its ImageNet performance, top1 error, 24.2%. I am a little bit confused about why the author here uses their implement result with a lower performance. In addition,  it is interesting that the author states that they can combine PC-DARTS with their neighbor-aware. However, they only show an S3 search space result in the appendix, it would be more convincing to show the neighbor-aware method's generalization ability if you can apply it on the standard search space and directly compare with PC-DARTS's public performance. Otherwise, the 'SOTA' statement looks not very strong for me.\n\n================================After Response==============================\n1. I agree that different DARTS paper usually uses some different settings, the lower PC-DARTS performance in the paper could be reasonable.\n2. Search Space design sometimes can greatly impact the result of the final result, but it makes sense to modify the search space for a better result. I am glad that you state the situation of the performance on the original DARTS space.\n3. I also read other reviewers' opinions. Based on the author's response and my previous rating, I decided to keep this score. This is an acceptable paper, but still has something to do in the future, like a more comprehensive experiment part.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RydFGH04m0f", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary \nThe authors proposed neighborhood-aware neural architecture search, where during the evaluation phase during search, the neighborhood of an architecture is considered. Specifically, when an architecture $\\alpha$ is picked, its neighbors $\\mathcal{N}(\\alpha)$ all contribute to the performance validation. This is built upon the assumption that `` flat minima generalize better than sharp minima’’ and the authors verify it in Appendix C. \nThe authors conducted experiments on CIFAR-10/100 and ImageNet, and obtained promising improvements over the standard baselines. \n\n** Clarify\n1.\tTowards \"Due to the property of the total variation distance, when $d$ is an integer, the neighborhood contains all the cells that have at most $d$ edges associated with different operations from $\\alpha$\". As you reported, $\\alpha$ is a collection of $\\alpha^{(i,j)}$, where each $\\alpha^{(i,j)}$ is a one hot vector “ But in DARTS, $\\alpha^{i,j}$ is a distribution of all candidate operations. In this case, how to select the $\\mathcal{N}(\\alpha)$?\n\n** Significance \nOverall, I think the results are solid.\n1.\tThere is a possible “ensemble’” baseline for your method. Let us take DARTS as an example. First, we independently train $n_{nbr}$ one-shot models. Each one-shot model has an individual $\\alpha$. Then, we sample an architecture from the average of all $\\alpha$’s. This could be another way to leverage neighborhood information and should be compared. \n2.\tImprovement not significant: In Table 4, compared to DARTS+, the improvement is 0.1/0.4 on CIFAR10/100. Compared to PDARTS, on the three datasets, the results between your method and PDARTS are almost the same. Therefore, you should apply your method to more recent advantaged methods to show that it is orthogonal or others.\n3.    As you pointed in Section 2, (Zela et al 2020) also observed a strong correlation between the generalization error of the architecture found by DARTS. It is good to see the exploration in Table 6. I think the \"NA-DARTS-ES\" should be implemented to see whether your method and  (Zela et al 2020) are complementary to each other. \n4.\tThe code should be released to reproduce your work.\n\n== Post Rebuttal ==\n\nI am satisfied with the response \"ensemble baseline\" and \"NA-DARTS-ES\". But my concern about \"Improvement not significant\" is not addressed, which is also mentioned by R1 and R4. I will remain my score as 6.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new NAS methods that when doing architecture search, returns flat minima using based on a notion of distance defined for two cells (Eq. (2)). Authors then evaluation the effectiveness of the proposed methods against prior work on several benchmarks.

As authors have discussed in the paper, the idea of using flatness notion in architecture search is not new and has been first proposed by Zela et al 2020. This paper is building on Zela et al 2020 but the proposed algorithm is novel and different than Zela et al 2020. Even though the introduced algorithm is interesting, there are several concerns/areas of improvements:

1- The proposed method's performance is highly dependent to the notion of distance defined in eq. (2). However, the current choice is not well-motived and does not seem like a well-thought-out choice. See for example the issue raised by R1. I think authors need to spend more time on this choice. One other option is to meta-learn the vector representation of each operation.

2- All reviewers agree that the improvements marginal and in some cases not statistically significant. Authors have responded by arguing that this is typical for this area of research. I don't find this answer satisfying. For example, consider P-DARTS (Chen et al., 2019). P-DARTS improves over NA-DARTS (the proposed method) on CIFAR-10 and ImageNet and on CIFAR-100 they are on par given the standard deviation of NA-DARTS (see Tables 4 and 5). Moreover, the search cost of P-DART is 0.27% of NA-DARTS (Table 4). So P-DARTS has clear advantage over NA-DARTS.

Given the above issues, I recommend rejecting the paper. I hope authors would take feedbacks from the reviewing process into account to improve the paper and resubmit.

Decision: Reject