ZARTS: On Zero-order Optimization for Neural Architecture Search
Authors: Xiaoxing Wang
Wenxuan Guo
Junchi Yan
Xiaokang Yang
Jianlin Su
Venue: ICLR 2022 Submitted (2022)

Abstract: Differentiable architecture search (DARTS) has been a popular one-shot paradigm for NAS due to its high efficiency. It introduces trainable architecture parameters to represent the importance of candidate operations and proposes first/second-order approximation to estimate their gradients, making it possible to solve NAS by gradient descent algorithm. However, our in-depth empirical results show that the approximation will often distort the loss landscape, leading to the biased objective to optimize and in turn inaccurate gradient estimation for architecture parameters. This work turns to zero-order optimization and proposes a novel NAS scheme, called ZARTS, to search without enforcing the above approximation. Specifically, three representative zero-order optimization methods are introduced: RS, MGS, and GLD, among which MGS performs best by balancing the accuracy and speed. Moreover, we explore the connections between RS/MGS and gradient descent algorithm and show that our ZARTS can be seen as a robust gradient-free counterpart to DARTS. Extensive experiments on multiple datasets and search spaces show the remarkable performance of our method. In particular, results on 12 benchmarks verify the outstanding robustness of ZARTS, where the performance of DARTS collapses due to its known instability issue. Also, we search on the search space of DARTS to compare with peer methods, and our discovered architecture achieves 97.54% accuracy on CIFAR-10 and 75.7% top-1 accuracy on ImageNet, which are state-of-the-art performance.

Under review as a conference paper at ICLR 2022
ZARTS: ON ZERO-ORDER OPTIMIZATION FOR NEU- RAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Differentiable architecture search (DARTS) has been a popular one-shot paradigm for NAS due its high efficiency. introduces trainable architecture parameters to represent the importance of candidate operations and proposes first/second- order approximation to estimate their gradients, making it possible to solve NAS by gradient descent algorithm. However, our in-depth empirical results show that the approximation will often distort the loss landscape, leading to biased ob- jective to optimize and in turn inaccurate gradient estimation for architecture pa- rameters. This work turns to zero-order optimization and proposes a novel NAS scheme, called ZARTS, to search without enforcing the above approximation. Specifically, three representative zero-order optimization methods are introduced: RS, MGS, and GLD, among which MGS performs best by balancing the accuracy and speed. Moreover, we explore the connections between RS/MGS and gradient descent algorithm and show that ZARTS can be seen as a robust gradient-free counterpart to DARTS. Extensive experiments on multiple datasets and search spaces show the remarkable performance of our method. In particular, results on 12 benchmarks verify the outstanding robustness of ZARTS, where the perfor- mance of DARTS collapses due its known instability issue. Also, we search on the search space of DARTS to compare with peer methods, and our discovered architecture achieves 97.54% accuracy on CIFAR-10 and 75.7% top-1 accuracy on ImageNet, which are state-of-the-art performance.
INTRODUCTION
Despite their success, neural networks are still designed mainly by humans (Simonyan & Zisserman, 2014; He al., 2016; Howard al., 2017). It remains open to automatically discover effective and efficient architectures. The problem of neural architecture search (NAS) has attracted wide attention, which can be modeled bi-level optimization for network architectures and operation weights.
One-shot NAS (Bender et al., 2018) is a popular search framework that regards neural architec- tures as directed acyelic graphs (DAG) and constructs supernet with all possible connections and operations in the search space. DARTS (Liu et al., 2019) further introduces trainable architecture pa- rameters represent the importance of candidate operations, which are alternately trained by SGD optimizer along with network weights. It proposes a first-order approximation to estimate the gra- dients of architecture parameters, which is biased and may lead the severe instability issue shown by (Bi et al., 2019). Other works (Zela et al., 2020b; Chen & Hsieh, 2020) point out that architecture parameters will converge to a sharp local minimum resulting in the instability issue and introduces extra regularization items so that architecture parameters converge to flat local minimum.
In this paper, we empirically show that the first-order approximation of optimal network weights sharpens the loss landscape and results in the instability issue of DARTS. It also shifts the global minimum, misleading the training of architecture parameters. To this end, we discard such approx- imation and turn to zero-order optimization algorithms, which run without the requirement that the search loss is differentiable w.r.t. architecture parameters. Specifically, we introduce a novel NAS scheme named ZARTS, which outperforms DARTS by large margin and can discover effi- cient architectures stably on multiple public benchmarks.
In nutshell, this paper sheds light the frontier of NAS in the following aspects:

---

Under review as a conference paper at ICLR 2022
1) Establishing zero-order based robust paradigm to solve bi-level optimization for NAS. Dif- ferentiable architecture search has been a well-developed area (Liu et al., 2019; Xu et al., 2020b; Wang et al., 2020b) which solves the bi-level optimization of NAS by gradient descent algorithms. However, this paradigm suffers from the instability issue during search since biased approximation for optimal network weights distorts the loss landscape, shown in Fig. 1 (a) and (b). To this end, we propose a flexible zero-order optimization NAS framework to solve the bi-level optimization problem, which compatible with multiple potential gradient- algorithms in the literature.
2) Uncovering the connection between zero-order architecture search and DARTS. This work introduces three representative zero-order optimization algorithms without enforcing the unverified differentiability assumption for search loss w.r.t. architecture parameters. We reveal the connections between the zero-order algorithms and gradient descent algorithm, showing that two implementa- tions of ZARTS can be seen as gradient-free counterparts to DARTS, being more stable and robust.
3) Strong empirical performance and robustness. Experiments on four datasets and five search spaces have been conducted to evaluate the performance of our method. Unlike DARTS that suffers the severe instability issue shown by (Zela et al., 2020b; Bi et al., 2019), ZARTS can stably dis- cover effective architectures various benchmarks. In particular, the searched architecture achieves 75.7% top-1 accuracy on ImageNet, outperforming DARTS and most of its variants.
2 RELATED WORK
One-shot Neural Architecture Search. Bender et al. (2018) construct a supernet so that all can- didate architectures can be seen as sub-graph. DARTS (Liu et al., 2019) introduces architecture parameters to represent the importance of operations in the supernet and update them by gradient descent algorithm. Some works (Xu et al., 2020b; Wang et al., 2020b; Dong & Yang, 2019) reduce the memory requirement of DARTS in the search process. Other works (Zela et al., 2020b; Chen &
Hsich, 2020) point out the instability issue of DARTS, i... ckip-connection gradually dominates the normal cells, leading to performance collapse during the search stage.
Bi-level Optimization for NAS. NAS can be modeled as a bi-level optimization for architecture pa- rameters and network weights. DARTS (Liu et al., 2019) proposes first/eccod approximations to estimate gradients of architecture parameters so that they can be trained by gradient descent algo- rithms. However, we show that such approximation will distort the loss landscape and mislead the training of architecture parameters. Amended-DARTy (Bi et al., 2019) derives an analytic formula of the gradient w.r.t. architecture parameters that includes the inverse of Hessian matrix of network weights. which is even unfeasible to compute. In contrast, this work discards the approximation in DARTS and attempts to solve the bi-level optimization by gradient- free algorithms.
Zero-order Optimization. Unlike mrudient-based optimization methods that require the objective differentiable w.r.t. the parameters, zero-order optimization can train parameters when the gradient of objective is unavailable or difficult to obtain, which has been widely used in adversarial robust- ness for neural networks (Chen et al., 2017; Ilyas et al., 2018), meta learning (Song et al., 2020), and transfer learning (Tsai et al., 2020). Liu et al. (2020b) aim at AutoML and utilize zero-order opti- mization to discover optimal configurations for ML pipelines. In this work, (to our best knowledge) make the first attempt to apply zero-order optimization to NAS and experiment with multiple algorithms, from vanilla random search (Flaxman et al., 2004) to more advanced and effective direct search (Golovin et al., 2020), showing its great superiority against gradient-basee methods.
3 BI-LEVEL OPTIMIZATION IN DARTS
Following ohe-shot NAS (Bender et al., 2018), DARTS constructs a supernet stacked by normal cells and reduction cells. Cells in the supernet are represented by directed acyclic graphs (DAG) with N nodes ( which represents latent feature maps. Each edge e4, contains multiple operations for..0 E O}, whose importance is represented by architecture parameters ag Therefore, NAS can be modeled as a bi-level optimization problem by alternately updating the operation weights w (parameters within candidate operations on each edge) and the architecture parameters a::
min (wor( (a)),
s.t. w" (ai) = arg min Lirain a).
2

---

Under review as a conference paper at ICLR 2022
DARIS
ZARTS-MGS ZAR
650
0.35
ZARTSRR
60
0.00
10.00,0223
-100 1275 -225 635 330 6n
-0.5 .250
-025 65s 3.00 o1s (c) Tracks of optimization path
(a) Landscape w.r.t. with Wist
(b) Landscape w.r.t. with w
Figure 1: Loss landscapes w.r.f. architecture parameters where the red star indicates the global minimum. (a) illustrates the landscape with wist- (b) illustrates the landscape with w', which is obtained by training for 10 iterations. To fairly compare the landscapes in (a) and (b), we utilize the same model and candidate a points. We observe the first-order approximation sharpens the landscape. (c) displays the tracks of optimization path of DARTS and our ZARTS. Starting at the same initial point, ZARTS can converge to the global minimum but DARTS fails.
3.1 FUNDAMENTAL LIMITATIONS IN THE DARTS FRAMEWORK
By enforcing an unverified (and in fact difficult to verify) assumption that the search loss few (w (ax) a is differentiable w.r.t. a, DARTS (Liu et al., 2019) proposes a second-order ap- proximation for the optimal weights w (a)) by applying one-step gradient descent:
w" RJ (a) w - Wwwaiinn (w, a) =w',
(2)
where & is the learning rate to update network weights. Thus the gradient of the loss function w.r.t. a, V Vafuallw" (w (a:), a). can be computed by the chain rule: Va a+) Va Vaaaai(w> a) <Và V Ctrain (w, ax) V Leat a). Nevertheless, the second-order partial derivative is hard to compute, so the authors adopt the difference method, which is proved in Appendix A.I.
To further reduce the computational cost, first-order approximation is introduced by assuming w (a) being independent of a, as shown in Eq. 3, which is much faster and widely used in many variants of DARTS (Chen et al., 2019; Wang et al., 2020b; Zela et al., 2020b).
(a()) (iee(())
The gradient is then simplified as: V Vafrarl""(a) = Vafral a)), which, however, further exacerbates the estimation bias.
Reexamining the definition of wn (a) in Eq. 1, one would note that it is intractable to derive mathematical expression for w= (ax), making Leat(w> (ax), cx) even non-differentiable w.r.t. a. Yet Eq. 2 and Eq. 3 that differentiability is
DARTS has to compromise with such upproximations established and SGD can be applied. However, such sketchy estimation of optimal operation weights distort the loss landscape w.r.t. architecture parameters and thus mislead the search procedure, which is shown in Fig. and analyzed in the next section.
3.2 DISTORTED LANDSCAPE AND INCORRECT OPTIMIZATION PROCESS IN DARTS
Fig. 1 illustrates the loss landscape with perturbations on architecture parameters showing how different approximations of wn affect the search process. We train a supemet for 50 epochs and ran- domly select two orthonormal vectors the directions to perturb directions is used to draw landscapes in Fig. 1(a) and (b) for a fair comparison. Fig. (aa shows the loss landscape with the first-order approximation in DARTS, (ee the loss landscape with more accurate w (a), which is obtained by fine-tuning the network weights for 10 iterations for each a. Landscapes (contours) are plotted by evaluating at grid points ranged from -1 to at an interval of 0.02 in both directions. Global minima are marked with stars on the landscapes, from which we have two observations: 1) The approximation wise the global minimum and sharpens the landscape which is the representative characteristic of in- stability issue as pointed out by (Zela et al., 2020b). 2) Accurate estimation for w" leads to a flatter landscape, indicating that the instability issue can be alleviated. Moreover, we display the landscape with second-order approximation wnnd in Appendix A.2, which is also sharp but slightly flatter than
The same group of perturbation
w, while Fig. ((b) shows
w shifts
A "sharp" landscape has denser contours than "flat" one.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1: ZARTS: Zero-order Optimization Framework for Architecture Search
Hyper-parameters:
Operation weights w, architecture parameters sampling number N, iteration number M, update estimation function (6.).
while not converged do
Sample candidates: {u; Ju:}i= and estimate optimal operation weights w" (a;) by descending Stran oz,) for M iterations, where o act Compute descent direction: u" = o (!u, w (ax
Update architecture parameters:
a u²:
The sampling strategies and update estimation functions ((-) for three different zero-order optimization algorithms detailed in Table 1.
Table Configuration of three methods used ZARTS scheme. The main difference lies meaning of function ((-): RS follows the traditional gradient estimation algorithms, MGS estimates the update according the improvement of loss function, while GLD uses direct search. Note that the ZARTS framework is general and can support configurations besides the listed ones.
Algorithm
Sampling strategy
Update estimation function øi (Lu: w (ax))
ZARTS-RS
u; ~ ((la)) ) any spherically symmetric distribution.
u
Ei=1 [C(a + nu)) L(x - - u. 2uN
p(d)
(Bq.
u; q(u(a). any proposal distribution.
ZARTS-MGS
ur
ΣN
Biu,lo) ctujla
(Eq. 10)
34-1, uniform distri- bution unit sphere.
ZARTS-GLD
u" arg min, (C(á)lá = á - a uz} (Eq. 12)
Fig. (a). Consequently, we discard the firs/ssecond-order approximation in DARTS and instead use more accurate wt coordinated with zero-order optimization.
Figure (c) shows the optimization paths of DARTS and three methods of ZARTS, illustrating how the approximation in DARTS affects the search process. Starting from the same randomly generated position, we update architecture parameters for 10 iterations by DARTS and ZARTS and draw the tracks of the optimization path. ZARTS can gradually converge to the global minimum, while DARTS converges an incorrect point.
4 ZERO-ORDER OPTIMIZATION FOR ARCHITECTURE SEARCH
This paper goes beyond the restrictive firs//second-order approximation in DARTS and proposes to train architecture parameters a in zero-order optimization manner, allowing for more accurate esti- mation for w (ax). The generic form of our ZARTS framework is outlined in Alg. 1. Specifically, we select three representative methods, including vanilla zero-order optimization algorithm, random search (RS) (Liu et al., 2020a), and two advanced algorithms: Maximum likellhoo Guided Param- eter Search (MGS) (Welleck & Cho, 2020) and GradientLess Descent (GLD) (Golovin al., 2020). They are presented in Sec. 4.1, 4.2, 4.3 also as preliminaries. Further, we theoretically establish the connection between ZARTS and DARTS, showing that ZARTS with RS and MGS optimizer can be seen as an expansion of DARTS. In the following, we use L(a) & Lvailw> (a), a) to denote the u),
(a)),
objective w.r.t. architecture parameters a E Rd (Eq. 1), and L(a + +u) & (w where u is the update for
4.1 ZARTS-RE VIA RANDOM SEARCH
Typical zero-order optimization methods have no access first-order gradient information and con- struct gradient estimators based on zero-order information, typically, the function evaluation, As discussed in (Liu al., 2020a), gradient estimation techniques can be categorized into different types based on the required number of function evaluations. One-point gradient estimator is one of the most popular algorithms (Liu et al., 2020a):
VaL(a): = ((d) L(a + puju,
(4)
4

---

Under review as a conference paper at ICLR 2022
where is sampled from spherically symmetric distribution 9, 0 is smoothing param- eter, and (o(d a ceneenienndeeendentt factor related to q. Specifically, q can either be a standard multivariate normal distribution (00. I) with sod) 1, multivariate uniform distribution unit sphere gd-1 with s(d) = d. Intuitively, ZARTS-RS samples nearby points from a and yields large updating step if the function value is high, consistent with the definition of the gradient.
Two-point gradient estimator is natural extension of one-point estimator:
Val(a)= = ((()) 2μ
[C(a + pu) - L(a - [uu) u.
(5)
We can also sample and average a batch of gradient estimations as Eq. to reduce the variance of gradient estimators, resulting in the multi-poti estimator:
:p(d)
Val(a)
Σ [C(a + pu,) L(a ju;) u, 2
(6)
Following the first-order gradient descent algorithms, the architecture parameters a are updated by a + a ((a(()) with the learning rate &. Our implementation is compatible with all the estimators above, and we multi point estimator (Eq. 6) by default.
4.2 ZARTS- -MGS VIA MAXIMUM-LIKELIHON GUIDED PARAMETER SEARCH
Maximum- likelihood guided parameter search (MGS) is an advanced zero-order optimization algo- rithm for machine translation (Welleck & Cho, 2020). We make the attempt to apply it to the NAS task. We first define a distribution for the update of architecture parameters, u, as follows:
p(ula)) = -((ula)
[[Laa + u) L(a)
exp
((a)
Z(a:)
where (u)a) exp (-I((c + u) [(T))/T) is an unnormalized exponential distribution, and Z(a) = ddu its normalization coefficient. t is temperature parameter controlling the variance of the distribution.
Intuitively, u with higher probability makes more significant improvement on the objective function. Therefore, the optimal update of architecture parameters be estimated by u Eu-p(ulaa) [u]. However, since the probability p(u ax) is an implicit function relying on L(a + u), making it impractical obtain the expectation, refer to (Welleck & Cho, 2020) and apply im- portance sampling to sample from a proposal distribution g(u(ax) with known probability function:
p(ula)
p(ula)
11= = Buup(ula))m [u]
udu ((ula))
u du
Z((x)
((x))((u
p(ula)
p(u:(a)
(uuu((uaa)
n1
- n"
Z(aa)q(u
N
((a))q(u:
where (u.), are sampled from the proposal distribution (u)().. Similarly, the normalization coefficient (())) can be computed as follows:
N
i u a
2(a:) = p(ula)du
(9)
For convenience, we define ratio representing the weight on each sample as ē(ula) = F(lo)) Consequently, the optimal update for architecture parameters in Eq. 8 can be computed by:
g(ula))
N
?(u Σ (u
exp (- (-[C(a + u:) (q())//)//(u/////
Σ
u
u
Σラ cxp (-[C(a + u,) ((a))//)//(ujlll
(10)
Finally, the architecture parameters are updated by a <- a + û Additional importance sampling diagnostics conducted verify the effectiveness of ZARTS-MGS (see results in Appendix A.3).
5

---

Under review as a conference paper at ICLR 2022
4.3 ZARTS-GLI VIA GRADIENTLESS DESCENT
Unlike the above two algorithms that estimate gradient or the update for a. Golovin al. (2020) propose the so-called Gradientl Less Descent (GLD) algorithm, which falls into the category of truly gradient-free (or direct search) methods. This work provides solid theoretical proof on the efficacy and efficiency of this approach and suggestions on the choice of search radius boundaries. Particu- larly, the authors prove the distance between the optimal minimum and the solution given by GLD is bounded and positively correlated with the condition number of the objective function, where the condition number Q defined as:
[C(a + A, [(a)) ||||| [
max ISiSK
S.
(11)
| [(a)]
We notice the loss landscape w.r.t is pretty flat, as shown in Fig. 1(b), implying a low condition number, thus the high efficiency of ZARTS-GLD.
Specifically, at each iteration, with predefined search radius boundary [r, [r, we indepen- dently sample candidate updates {u:} for architecture parameters on spheres with various radii
k=0 {2 [2=*R)les0/r (o/( and perform function evaluation at these points. By comparing L(ax) and {C(e +
u.)]. a steps to the point with minimum value, or stay at the current point if none of them makes an improvement. The architecture parameters are then updated by a t- u".
u' arg t
((á))l a, a
(12)
4.4 CONNECTION BETWEEN DARTS AND ZARTS The similarity between rradient-stiimation-- based zero-order optimization and SGD builds an es- sential connection when the objective function is differentiable. Recall the smoothing parameter defined in Eq. 4, leading to the following definition of the smoothed version of L:
fa(a) == Eu-ay [C(x su)),
(13)
where o' = NV q= I). and o' Bd (a multivariate uniform distribution on a unit ball) if q- = gd-1 The unbiasedness of Eq. 4 with respect to V. (a) is assured by:
Eusay Val(a)] (aL)(a),
(14)
as proved by (Nesterov & Spokoiny, 2017; Berahas et al., 2021). The two-point and multi-point estimates have a similar unbiasedness condition when Eurq [u] = 0, which is satisfied in our case.
The bias between V(((a) and vaL(a) is also bounded (Berahas et 2021; Liu et al., 2018b):
E [iIta[(a)- v.L(a)1 =())IV=<(a)] (1
(1'd+ + +udd
(15)
(dd)
where d, u4, (p(d have the same meanings as those in Sec. 4.1. Consequently, if L(a) is indeed differentiable w.r.t a and the iteration number M is set to 1, ZARTS-RS degenerates to second- order DARTS with bounded error.
Next, we theoretically show that MGS (Welleck & Cho, 2020) will degenerate to gradient descent al- gorithm if the first-order Taylor approximation is applied. Then we analyze the relationship between ZARTS-MGS and DARTS.
Proposition 1. Assuming that C(a) in Eq. is differentiable w.r.t. a. MGS algorithm (Welleck & Cho, 2020) degenerates to SGD (used in vanilla DARTS) by the first-order Taylor approximation for L(ox), i.e., u² V.).()).
Proof. Denote g & VaL(a) the gradient of L. The Taylor series of L at up to the first order gives L(a+ - -(aa) R un Applying this approximation to the distribution of u (Eq. 7) yields:
g/T
p(uaa)
7(g) 7(g) = Juule
g/Tdu.
(16)
Here, the magnitude of u is constrained within & to make sure the rationality of first-order Taylor approximation. The optimal update u" then becomes:
u' S Se u-e g/Tdu
VgZ(g)
1
= =- In Z(g).
(17)
2(g)
+Z(agg)

---

Under review as a conference paper at ICLR 2022
Note that u g -|lu|llg| where is the angle between and g. According to the symmetry of integral, (g) is determined once [ is given. Therefore, we can formulate (gg) as a function
of |ggl: Z(g) = ([lg])). According the chain rule:
u = V (gg) = Vg In ((lgl) = V 2 7(lgl)
Vilsl ((Ig))) TZ( (1gg [ggl g. (18)
V 9
Since Z(1gg)) V lgl (() ||&||
are all scalars, we have
x - - Vaf(a) - Vaf (a))
(19)
That is, the optimal update u* in MGS algorithm shares a common direction with the negative gradient - [(),,,, used by gradient descent.
Based on Proposition 1, ZARTS- can be seen as an expansion of DARTS, and it degrades to first-order and second-order DARTS when w' is estimated by wist and Wind respectively. In
general, ZARTS-RS/-MGS can degenerate to DARTS, given the differentiability assumption.
However, unlike DARTS, which has estimate w' (ax) by wist or wind satisfy the differentiablity property of Leat and update a by gradient descent algorithm, ZARTS, without such assumptions, can compute w* (ax by training network weights for arbitrary numbers of iterations, leading to more robust and effective training for architecture parameters, as shown in the next section.
5 EXPERIMENTS
In this section, we first verify the stability of our ZARTS (with its three variants RS, MGS, GLD) on the four popular search spaces R-DARTS (Zela al., 2020b) on three datasets including CIFAR- 10 (Krizhevsky et al., 2009), CIFAR-100 (Krizhevsky et al., 2009), and SVHN (Netzer al., 201 Note that though ZARTS-GLD performs best Table 2, and it falls into the category direct search methods, requiring
sampling for candidate updates u and thus more search cost (2.2 GPU-days on the search space of DARTS) than ZARTS-MGS (1.0 GPU-days). Considering the trade-off between accuracy and speed, ZARTS-MGS is chosen by default if not otherwise specified. We then follow Amended-DARTS (Bi et al., 2019) and empirically evaluate the convergence ability of method by searching for 200 epochs. Performance trends of the discovered architectures along with the search process are drawn in Fig. 2(a). Finally, we search and evaluate on the search space of DARTS (Liu et al., 2019) compare with peer methods and show the efficacy of our method. All the experiments are conducted on NVIDIA 2080Ti. The details of search spaces and experiment settings are given in Appendix B, due to space limitation.
5.1 STABILITY EVALUATION
The instability issue of gradient- based NAS methods has re- cently drawn increasing attention. Amendee-DARRT. (Bi et al., 2019) shows that after search- ing by DARTS for 200 epochs, skip-connection gradually domi- nates the discovered architectures.
Table 2:
Test error (%) with DARTS and its variants different search spaces. We adopt the same settings as R-
DARTS (Zela al., 2020a). The best and second best is underlined in boldface and in boldface, respectively.
R-DARTS
DARTS
ZARTS (ours)
DARTS
DP
1.2
FS
ADA
RS
MGS
GL.D
SVHN CIFARIO0 CO
S1
3.84
3.11
2.78
3.01
3.10
2.83
2.65
2.50
S2
4.85
3.48
3.31
3.26
3.35
3.35
3,24
3.08
R-DARTS (Zela et al., 2020b)
S3
3.34
2.93
2.51
2.74
2.59
2.59
2.56
2.56
proposes four search spaces, S1-S4,
S4
7.20
3.58
3.56
3.71
4.84
4.90
3.70
3,52
which amplify the instability of DARTS, as such dominance occurs
S1
29.46
25.93
24.25
28.37
24.03
23.64
23.16
23.33
S2
26.05
22.30
22.24
23.25
23.52
21.54
20.91
21.13
after only 50 epochs of searching.
S3
28.90
22.36
23.99
23.73
23.37
22.62
22.33
21.90
These studies expose the instability
S4
22.85
22.18
21.94
21.26
23.20
23.33
21.31
21.00
of gradient-based methods. To verify the stability of our method,
S1
4.58
2.55
4.79
2.72
2.53
2.40
2.51
2.48
S2
3.53
2.52
2.51
2.60
2.54
2.52
2.45
2.48
S3
3.41
2.49
2.48
2.50
2.50
2.41
2.52
2.44
search S1-$4 proposed by R-DARTS and conduct convergence analysis following Amended-DARTS
S4
3.05
2.61
2.50
2.51
2.46
2.59
2.48
2.53
Performance on S1-S4. We first search on the four spaces on CIFAR-I0, CIFAR-100, 100, and SVHN. Our evaluation settings are the same R-DARTS (Zela et al., 2020b). Specifically, for CIFAR-10,
7

---

Under review as a conference paper at ICLR 2022
97.6
Num. of Parameters (M)
Top-1 Accuracy (%6)
97.4
4,0
3.5
97.2
97.0
ZARTS
2.5
ZARTS
96.8
2.0
100
125 Epoch
150
175
100
125
150
175
200
Epoch
(a) Trend of Top-1 accuracy
(b) Trend of Number of Parameters
Figure 2: Trends of accuracy and model size in the search process of DARTS and ZARTS for 200 epochs on CIFAR-10. The top-1 accuracy is obtained by training models for 600 epochs.
Table 3: Performance
CIFAR. The top block reports the accuracy of the best model. The bottom block gives the mean of four independent searches as recommended by (Zela et al., 2020b; Chen & Hsieh, 2020; Yu al., 2020). Reported by (Dong Yang, 2019). by (Zela et al., 2020b).
Params
Error
GPU Cost
Params
Error
GPU Cost (days)
CIFAR-10
CIFAR-100
(M) 4
(%) 4
(days)
(M) +
(%)
DARTS (1st) (2019)
3.3
3.00
0.4
AmocbaNet (2019)
3.1
18,93
3150
DARTS (2nd) (2019)
3.4
2.76
1.0
PNAS (0)
3,2
19.53
150
P-DARTS (2019)
3.4
2.50
0.3
ENAS (2018)
4.6
19.43
0.45
GDAS (2019)
3.4
2.93
0.2
P-DARTS (2019)
3.6
17.49
0.3
ISTA-NAS (2020)
2.54
0.05
GDAS (2019)
18.38
0.2
PR-DARTS (2020)
2.32
0.17
ROME (2020a)
DARTS- (2021)
3.5
2.50
0.4
PR-DARTS (2020)
0.17
ZARTS (ours)
3.5
2.46
DARTS- (2021)
0.4
ZARTS (ours)
15,46
1.0
DARTS(1s() (2020)
3.38
0.4
MergeNAS (2020b)
2.9
2.68
0.6
avorago
DARTS (2019)
20.58=00.44
0.4
averuge
SGAS (Cri.2) (2020)
3.9
2.67-10.21
0.3
R-DARTS (2020h)
18.01=0.226*
1.6
R-DARTS (2020h)
2.95
1.6
ROME (2020a)
4.4
17.414:0.12
0.3
SDARTS-ADY (2020)
3.3
2.61
1.3
DARTS- (2021)
3.3
17.51
0.4
Amended-DARDE (2019)
3.3
2.71
1.7
ZARTS (ours)
4.1
16.29:t0.53
1.0
DARTS- (2021)
0.5
2.59:10.08
0.4
ZARTS (ours)
3.7
2.54
1.0
the discovered models on S1 and S3 are constructed by 20 cells with 36 initial channels; models on $2 and $4 have 20 cells with 16 initial channels. For CIFAR-100 and SVHN, all the models on S1-$4 have 8 cells and 16 initial channels. Four parallel tests are conducted on each bench- mark, among which the best reported Table 2. We observe that ZARTS achieves outstanding performance with great robustness on 12 benchmarks. All three zero-order algorithms outperform DARTS by a significant margin. Even the vanilla zero-order optimization algorithm ZARTS-RS achieves similar robust performance coarse estimation wist in DARTS distorts the landscape and causes instability. Additionally, to compare with SDARTS (Chen & Hsieh, 2020), follow its experiment settings by increasing the number cells and initial channels to 20 and 36 with results reported Appendix B.4.
R-DARTS, which verifies analysis in Fig. 1, i.e., the
Convergence Analysis. The convergence ability of NAS methods describes whether search method can stably discover effective architectures along the search process. For an effective NAS method with great convergence ability, the discovered architectures' ultimate performance (top-1 accuracy) should converge to a high value. Amended-DARTl (Bi et al., 2019) empirically shows that DARTS has a poor convergence ability: accuracy the supernet increases but the ultimate per- formance of the searched network drops. Following Amended-DARTI we run ZARTS and DARTS for 200 epochs and show the trend of performance and number of parameters in Fig. Specifically, we derive one network every 25 epochs during the search process and train each network for 600 epochs to evaluate its ultimate performance. We observe that the networks searched by ZARTS per- form stably well (around 97.40% accuracy), while the performance of networks searched by DARTS gradually drops. Moreover, the parameter number of networks searched by DARTS decreases sig- nificantly after 50 epochs. indicating that parameterless operations dominate the topology and the instability issue (Zela et al., 2020a) occurs. On the contrary, ZARTS consistently discovers effective networks with about 4.0M parameters, showing the great stability of method.
8

---

Under review as a conference paper at ICLR 2022
5.2 COMPARISON WITH PEER METHODS ON THE SEARCH SPACE OF DARTS
To show the efficacy and effectiveness of our method, we search and evaluate on DARTS's search space both CIFAR-10 and CIFAR-I00. Additionally, the models searched on CIFAR-10 transferred to ImageNet to evaluate the transferability of our method. The search space and settings follow DARTS (Liu et al., 2019), as introduced in Appendix B.2.
Results on CIFAR-10. We conduct four parallel runs by searching with different random seeds and separately training the searched architectures for 600 epochs. The best and average accuracy of four parallel tests are reported in Table 3. In particular, ZARTS achieves 97.46% average accuracy and 97. 754% best accuracy on CIFAR-10, outperforming DARTS and its variants, Also, compared with Amended-DARTS that approximates optimal operation weights w' (ax by Hessian matrix, our method can stably discover effective architectures in fewer GPU days.
Results on CIFAR-100. Table 3 shows our method achieves 83.71% 1 and 84.54% for mean and best accuracy (i.c. 1- cr on CIFAR-100, outperforming the compared methods by more than 1%.
Results ImageNet. For transfer- ability test, we follow the settings of DARTS to transfer the network discov- ered on CIFAR-10 to ImageNet. Mod- els constructed by stacking 14 cells with 48 initial channels. We train 250 epochs with batch size of 1024 by SGD with a momentum of 0.9 and a base learning rate of 0.5. We utilize the same data pre pre-processing strategies and auxiliary classifiers as DARTS. Table 4 shows the performance of our searched networks, wit two models evaluated. ZARTS (5.6M) has 5.6M parameters and achieves 75.7% top-1 accuracy the validation set of Im- ageNet, and ZARTS (5.0M) has 5.0M parameters and achieves 75.5% accu- racy, Their structure details are given in Appendix B.6, which has fewer skip connection operations than DARTS.
Table 4: Performance on ImageNet in DARTS's ' search space by two architectures. direct search on ImageNet.
FLOPs Params Top-1 Err. GPU Cost
Models
(M)
(M) L
(%) 4
(days)
AmoebuNct-A (2019)
555
5.1
25.5
3150
NASNet-A (2018)
564
5.3
26.0
1800
PNAS 8a)
588
5.1
25.8
225
MdeNAS (2019)
6.1
25.5
0.16
DARTS (2nd) (2019)
574
4.7
26.7
1.0
P-DARTS (2019)
557
4.9
24.4
0.3
PC-DARTS (2020a)
586
25.1
0.1
FairDARTS-B (2020)
541
24.9
0.4
FairNAS-CT (2019)
321
4.4
25.3
12
SNAS (2019)
$22
4.3
27.3
1.5
GDAS (2019)
581
26.0
0.2
SPOST (2019)
323
3.5
25.6
12
ProxylessNASt (2019)
465
7.1
24.9
8.3
FBNet-CI (2019)
375
5.5
25.1
9
Amended-DARRTS (2019)
586
5.2
24.7
1.7
ZARTS (5.6M params)
647
5.6
24.3
1.0
ZARTS (5.0M params)
573
5.0
24.5
1.0
FURTHER DISCUSSION AND CONCLUSION
The proposed ZARTS has opened new possible space for future work at least in the following as- pects: i) We have incorporated the three adopted zero-order solvers in Table 1, which suggests new solvers may also be readily reused to improve ZARTS, e.g., in a way of AutoML that automatically determines the suited solver given specific tasks or datasets. In contrast, this feature is not allowed in DARTS as there is little option for the gradient-descent solver. ii) Since ZARTS can be seen as a gradient-free counterpart DARTS, which fact also requires the same exhaustive GPU memory as DARTS, memory-efficient techniques, e.g., single-path NAS ROME (Wang et al., 2020a) can also be adopted reduce the memory cost well the computation cost in the search process.
DARTS has been a dominant paradigm in NAS, while its instability issue has received increasing attention (Bi et al., 2019; Zela et al., 2020b; Chen & Hsich, 2020). In this work, we have empiri- cally shown that the instability issue results from the first-order approximation for optimal network weights and the optimization gap DARTS, which is also raised in the recent study (Bi al., 2019). To step out of such a bottleneck, this work proposes robust search framework named ZARTS, allowing for higher-order approximation for (a()) and supporting multiple combinations zero- order optimization algorithms. Specifically, we adopt three representative methods for experiments and reveal the connection between ZARTS and DARTS. Extensive experiments on various bench- marks show the effectiveness and robustness of ZARTS. To our best knowledge, this is the first work that manages to apply zero-order optimization to one-shot NAS, which provides a promising paradigm solve the bi-level optimization problem for NAS.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understand- ing and Simplifying One-Shot Architecture Search. In ICML, pp. 549-558, 2018.
Albert Berahas, Liyun Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, pp. 1-54, 2021.
Kaifeng Bi, Changping Hu, Lingxi Xie, Xin Chen, Longhui Wei, and Qi Tian. Stabilizing darts with amended gradient estimation on architectural parameters. arXiv preprint arXiv:1910.1183) 2019.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware. In ICLR, 2019.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. ZOO: zeroth order op- timization based black-box attacks deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec@ CCS 2017, Dallas, TX, USA, November 3, 2017. pp. 15-26, 2017. doi: 10.1145/3128572.55 140448.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. In ICML, 2020.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive Differentiable Architecture Search: Bridg- ing the Depth Gap between Search and Evaluation. In ICCV, 2019.
Xiangxiang Chu, Bo Zhang, Ruijun Xu, and Jixiang Li. FairNAS: Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search. arXiv preprint. 1oXiv:1907.01855 2019.
Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li. Fair darts: Eliminating unfair advantages in differentiable architecture search. ECCV, 2020.
Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. DARTS- robustly stepping out of performance collapse without indicators. In ICLR. OpenReview.net, 2021.
Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A Lcrge-Scale Hierarchical Image Database. In CVPR, pp. 248 188-255, IEEE, 2009.
Xuanyi Dong and Yi Yang. Searching for a Robust Neural Architecture in Four GPU Hours. In CVPR, pp. 1761-1770, 2019.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gra- dientless descent: High-dimensional zeroth-order optimization. In ICLR. OpenReview.net, 2020.
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 preprint. AxKiv:904.00000 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In CVPR, pp. 770-778, 2016.
Andrew 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 preprint. orXiv: 04861, 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmätsson Stockholm, Sweden, July 10-15, 2018, pp. 2142-2151, 2018.
10

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer, 2009.
Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Müller, Ali Thabet, and Bernard Ghanem. Sgas: Sequential greedy architecture search. In CVPR, 2020.
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, pp. 19-34, 8a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable Architecture Search. In ICLR, 2019.
Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. arXiv preprint 1005..7805.10367, 2018b.
Sijia Liu, Pin-Yu Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero III, and Pramod K Varshney. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):33544 2020a.
Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy, Djallel Bouneffouf, Gregory Bramble, Horst Samu- lowitz, Dakuo Wang, Andrew Conn, and Alexander Gray. An ADMM based framework for automl pipeline configuration. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4892 4899, 2020b.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NIPSW, 2011.
Art B. Owen. Monte Carlo theory, methods and examples. 2013.
Hieu Pham, Melody Y Guan, Barret Zoph, Quoc V Le, and Jeff Dean. Efficient Neural Architecture Search via Parameter Sharing. In /CML, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In AAAI, volume 33, pp. 4780-4789, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:
2014.
Xingyou Song, Wenbo Gao, Yuxiang Yang, Krzysztof Choromanski, Aldo Pacchiano, and Yun- hao Tang. ES-MAML: simple hessian- free meta learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Yun- Yun Tsai, Pin-Yu Chen, and Tsung- Yi Ho. Transfer learning without knowing: Repro- gramming black-box machine learning models with scarce data and limited resources. CORR, abs/2007.0871 2020.
Xiaoxing Wang, Xiangxiang Chu, Yuda Fan, Zhexi Zhang, Xiaolin Wei, Junchi Yan, and Xiaokang Yang. ROME: robustifying memory-efficient NAS via topology disentanglement and gradients accumulation. CoRR, abs/2011.11233. 2020a.
Xiaoxing Wang, Chao Xue, Junchi Yan, Xiaokang Yang, Yonggang Hu, and Kewei Sun. Mergenas: Merge operations into one for differentiable architecture search. In International Joint Conference Artificial Intelligence, 2020b.
Sean Welleck and Kyunghyun Cho. Mle-guided parameter search for task loss minimization in neural sequence modeling. arXiv preprint urXiv:2006.01558 2020.

---

Under review as a conference paper at ICLR 2022
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang. Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. FBNet: Hardware-Awar Efficient ConvNet Design via Differentiable Neural Architecture Search. In CVPR, 2019.
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. Pe-darts: Partial channel connections for memory-efficient architecture search. In ICLR, 2020a.
Yuhui Xu, Lingxi Xic, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search. In ICLR, 2020b.
Yibo Yang, Hongyang Li, Shan You, Fei Wang, Chen Qian, and Zhouchen Lin. ISTA-NAS: efficient and consistent neural architecture search by sparse coding. NeurIPS, 2020.
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, 2020a.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020b.
Xiawu Zheng, Rongrong Ji, Lang Tang, Baochang Zhang, Jianzhuang Liu, and Qi Tian, Multinomial Distribution Learning for Effective Neural Architecture Search. In ICCV, pp. 1304-1313, 2019.
Pan Zhou, Caiming Xiong, Richard Socher, and Steven Chu-Hong Hoi. Theory-inspired path- regularized differential network architecture search. In NeurIPS, 2020.
Barret Zoph. Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning Transferable Architec- tures for Scalable Image Recognition. In CVPR, volume 2, 2018.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 ESTIMATION FOR RECOND-ORDER PARTIAL DERIVATIVE DARTS
Liu al. (2019) introduce second-order approximation to estimate optimal network weights, ie.. w¹ ~ w 3 - Ww (w,a), a), so that Va (a), a) & Vo a)
<V VVawwrraan (w,
a). However, the second-order partial derivative is hard com- pute, so the authors estimate it as follows:
Vaw Strain (w, a V Loat a) Valerain ox) Va (w ,x)
(20)
2c
where wt + V ( .)) and (ow Here, we prove that the above
approximation in Eq. 20 difference method.
Proof. First of all, to simplify the writing, make the following definitions:
f(w, ax) = V Ltrain a); g(w, a:) = Loaa o.).
(21)
Then the left term in Eq. 20 can be simplified as:
V2 a.w Vw Cirain Vw Cwailw', a) = Vuf(w.a) Vwg(w',a)
(22)
= a) Vwrglw', a)
(wrg(we, a)ll = Vuf(w,)) 1. \V ,0)l2. (23)
[V a2
where I Farnlw is a unit vector. We notice Vw/ a)) I is the directional derivative of (
f(w, a)) along direction which can be estimated by difference method with a small perturbation 0.01:
Vul(w, a) 7. /wr aill2 s flw + (l, f(w cl),a)
VV a)ll
(24)
26'
Moreover, we define [V Then w +el = w + t Wwwglwww wt so Eq. 24 can be simplified as:
flw + el), f(w fww-wll,0 ell,a) Verg(w oz)l2 flw aa) a) s(w a)
(25)
2c'
Substituting f(w, a)) Eq. 21 with Eq. 25 results Eq. 20. Therefore second-order approximation
in DARTS utilizes difference method, which is also zero-order optimization algorithm.
A.2 LOSS LANDSCAPE W.R.T. ARCHITECTURE PARAMETERS
To draw loss landscapes w.r.t. a. train supernet for 50 epochs and randomly select two thonormal vectors as the directions to perturb a. The same group of perturbation directions used draw landscapes for fair comparison. Landscapes plotted by evaluating at grid points ranged from -1 to 1 at an interval of 0.02 in both directions. Fig. 3 illustrates landscapes (contours)
1.0
1.0
1.0
3.5
-12
-025
-2.5
2.0 455
258 615
100
2018 .008 428 125
399 228 640 630 650 3
(a) Landscape w.r.t & with wist
(b) Landscape w.r.t. & with Wind
(c) Landscape w.r.t. with
Figure 3: Loss landscapes w.rt. architecture parameters Q. In (a), we illustrate the landscape with first-order approximation. In (b), we illustrate the landscape with second-order approximation. In (c), we obtain w' by training network weights w for 10 iterations, and illustrate the landscape w.r.t. a with w.. To fairly compare the landscapes, we utilize the same model and candidate points. We observe the firs//seonnd-orde approximations both sharpen the landscape.
13

---

Under review as a conference paper at ICLR 2022
w.r.t a under different order of approximation for optimal network weights, showing that both first- and second-order approximation sharpen the landscape and in turn lead to incorrect global mini- mum. In this work, we obtain w (ax by fixing and fine-tuning network weights for M iterations (Fig. (c)). Selection of M is also analyzed in Appendix B.3, showing that M = 10 iterations is accurate enough estimate optimal network weights.
A.3 DETAILS OF ZARTS-MGS ALGORITHM
Sclection of the Proposal Distribution q(ula)). Since the probability function of distribution p is intractable, we sample from a proposal distribution and approximate the optimal update of architecture parameters by Eq. 10. The proposal distribution q affects the efficiency of sampling. Specifically, an ideal should be as close to p as possible when the sampling number is limited. Following Welleck & Cho (2020), we set the proposal distribution q to mixture of two Gaussian distributions, one of which is centered at the negative gradient of the loss function with current weights:
- ax), a)) + NV
(26)
where a the standard deviation. Intuitively, finst-order DARTS (Liu et al., 2019) gives hint: it updates the architecture parameters in the direction of - V ao a).. The gradient is an imperfect but workable direction with easy access.
Importance Sampling Diagnostics. To demonstrate that importance sampling and our choice of the proposal distribution indeed appropriate in our case, we evaluate the effectiveness (the proposal distribution) quantitatively by the following experiments. According Owen (2013), ef- fective sample size (ESS) N. is a popular indicator defined as N₂ = E of For N samples, a
larger N₂ E [1, .] usually indicates a more effective sampling. On the contrary, small Ne implies imbalanced sample weights and therefore is unreliable (Owen, 2013).
To evaluate the effectiveness of sampling in ZARTS-MGS we set the sampling number N to various values and plot Ne versus epochs in each case. As is shown in Fig. 4(a), Ne gradually approaches N in all settings, indicating that different sampling numbers in our setting are meaningful, including larger ones (otherwise N₂ may "saturate").
As further exploration, we define effective sample ratio (ESR) R. as the ratio of effective sampling all samples:
N N
(27)
The value of Rg denotes the bias between the target distribution p and proposal distribution g, and smaller value indicates greater difference. Re is plotted against epochs for various N in Fig. 4(b). On the one hand, Rg at epoch 50 stabilizes 0.7 as N increases, which is an acceptable level of bias between and q and supports our choice of q on the other hand, we notice R, has already converged when N 4. Considering the trade-off between estimation accuracy and speed, we set N 4 as default, which is further discussed in Appendix B.3.
1.0
10
N-
N-8
N=2
N-8
N=4
N-10
Effective Samping Ratio
Nud
N-10
N=6
N-6
Effective Sampling
0.6
6-
4-
0.4
2
0.2
0
0.0
10
15
20
25
30
35
45
50
10
15
20
25
30
35
40
50
Fpoch
Fpoch
(a) ESS N. versus epochs over sampling number N. (b) ESR R. versus epochs over sampling number N.
Figure 4: ESS N₂ and ESR R, versus epochs with different sampling numbers N in the search stage on CIFAR-10. We fix iteration number M = 10 for all settings.
14

---

Under review as a conference paper at ICLR 2022
B SUPPLEMENTARY EXPERIMENTS
B. DETAILS OF SEARCH SPACES
DARTS's Standard Search Space. The operation set O contains 7 basic operations: skip
nection, max pooling, average pooling, 3 x 3 separable convolution, x separable convolution, 3 x 3 dilated separable convolution, and 5 x 5 dilated separable convolution. Though zero operation is included in the origin search space of DARTS (Liu et al., 2019), it will never be selected in the searched architecture. Therefore, remove zero operation from the search space. We search and evaluate on the CIFAR-10 (Krizhevsky et al., 2009) dataset in this search space, and then transfer the searched model ImageNet (Deng et al., 2009). Additionally, in our convergence analysis, search by DARTS and ZARTS in this search space for 200 epochs.
RDARTS's Search Spaces $1-S4. To evaluate the stability of search algorithm, RDARTS (Zela et al., 2020a) designs four search spaces where DARTS suffers from instability severely, i.c. normal cells are dominated by parameter-less operations (such as identity and max pooling) after searching for 50 epochs. In S1, each edge in the supernet only has two candidate operations, but the candidate operation set for each edge differs; in S2, the operation set O only contains x separable convolu- tion and identity for all edges; in S3, O contains 3 x 3 separable convolution, identity, and zero for separable convolution and noise operation for all edges. Please
all edges; in S4, O contains refer to Zela et al. (2020a) for more details of the search spaces.
B.2 EXPERIMENT SETTINGS
Search Settings. Similar to DARTS, we construct a supernet by stacking 8 cells with 16 initial channels. We apply Alg. I to train architecture parameters a for 50 epochs. Two hyper-parameters of ZARTS, sampling number N and iteration number M, are set to 4 and 10 respectively. Ablation studies of the two ayper-parametend are analyzed in Appendix B.3. The setup for training w follows DARTS: SGD optimizer with momentum of 0.9 and a base learning rate of 0.025. Our experiments are conducted on NVIDIA 2080Ti. ZARTS-MGS algorithm used in supplementary experiments by default.
Evaluation Settings. We follow DARTS (Liu et al., 2019) and construct models by stacking 20 cells with 36 initial channels. Models are trained for 600 epochs by SGD with a batch size of 96. Cutout and auxiliary classifiers are used as introduced by DARTS.
B.3 ABLATION STUDIES
There are two pypeeepprammttrs in our method: sampling number N and iteration number M. As introduced in Section 4, N samples of update step of architecture parameters u, are drawn to esti- mate the optimal update u*, For each sampled u, we approximate the optimal weights w w + u,) for each sample by training w for M iterations. To evaluate the sensitivity of our method to the two hyper-parametert above, we conduct ablation studies on the standard search space of DARTS on CIFAR-10 10 dataset.
Sensitivity the Sampling Number N. For various sampling numbers N, the average performance of three paral- lel searches with different random seeds is reported in Table 5. In this experi- ment, iteration number M is fixed to 10. When = 2, ZARTS achieves 97.37% accuracy with 2.87M parameters. The number of parameters of searched net- work increases N increases, and the performance of searched network gets stable when N > 4. Our method per- forms better than DARTS when N = 4, with similar search cost (1.0 GPU days). When N 6, ZARTS achieves its best accuracy (97.49%) and costs 1.1 GPU days. When N continues to increase, our method attempts to find more complex architectures (with 4.3 MM and 4.26M parameters).
Table 5: Comparison of different sampling numbers to approximate the optimal update for architecture parame- ters on the standard search space of DARTS on CIFAR- 10 dataset. For each N, three parallel tests are conducted by searching on different random seeds and the mean and standard deviation of top-1 accuracy are reported.
Sampling number
N=
N=4
N=
N=8
Error (%)
2.63
2.54
2,51
2.57
STD)
+0.12
+0.07
+0.09
+0.11
Params (M)
2.87
3.71
3.53
4.31
Cost (GPU days)
0.5
1.0
1.1
1.5
15

---

Under review as a conference paper at ICLR 2022
Table 7: Comparison with peer methods under the settings of SDARTS. (left) Test error of other methods are obtained from SDARTS (Chen & Hsich, 2020), indicating the best performance among four replicate experiments with different random seeds. Note that 'RS' in SDARTS indicates random smoothing technique, while 'RS' in ZARTS indicates random search, zero-order optimization algorithm. The best and second best is underlined in boldface and in boldface, respectively. (right) We report the average error and standard deviation of our method among four replicate experiments. Since PC-DARTS and SDARTS do not provide the average performance, we only compare the three implementations of our ZARTS.
SDARTS
ZARTS
ZARTS (avg.
PC-DARTS
RS
ADV
RS
MGS
GL.D
RS
MGS
GLD
CIFARIO
SI
3.11
2.78
2.73
2.83
2.65
2.50
S1
3.10+10.00
2.79
0.77
SHHS CI CIFARI6
S2
3.02
2.75
2.65
2.41
2.39
2.60
S2 2.60:1..14
2.65
2.67
S3
2.51
2.53
2.49
2.59
2.56
2.56
S3 2.89
2.7420.10
2.70
S4
3.02
2.93
2.87
3.35
2.74
2.63
S4 4.11+1.007
2.99-10.1
0.35
SVHN CIFARIO
S1
18.87
17.02
16.88
17.38
17.62
17.40
S1 18.07
18.20:0.48
17.8310444
S2
18.23
17.56
17.24
16.05
16.41
16.69
S2 17.04
17.35 17.14
S3
18.05
17.73
17.12
17.22
17.03
16.58
S3 18.14
17.72=0.46
16.99-0.38
17.16
17.17
15.46
18.23
16.57
15.97
S4 19.08
17.3310.73
16.63.10.55
S1
2.28
2.26
2.16
2.09
2.13
2.14
S1 2.21
2.17
2.20
$2
2.39
2.37
2.07
2.06
2.06
2.15
S2
2.16+0.10
2.10:0003
0.22
S3
2.27
2.21
2.05
2.17
2.20
2.07
S3 2.27::0.14
2.25
2.13
S4
2.37
2.35
1.98
2.49
2.04
2.15
S4 2.56.10.09
0.20
2.26
Sensitivity to the Iteration Number M. DARTS and its variants (Xu et al., 2020b; Zela et al., 2020b) assume that the optimal operation weights w" (ax is differentiable w.r.t. architecture param- eters a. which has not been thcoreti- cally proved. In this work, we relax the above assumption and adopt zero-order optimization to update a. As introduced Section 4, we perform multiple iter- ations of gradient descent on operation weights to accurately estimate w (ax). To further confirm our analysis on the impact of iteration number M, we search with various values of M and report the average performance of three paral- lel searches with different random seeds in Table 6. In this experiment, we set the sampling number N 4. The results reveal that the performance of searched model improves as M increases and the highest accuracy is achieved at M = 10, which supports our analysis that inaccurate estimation for optimal operation weights w" (ax can mislead the search procedure.
Table 6: Comparison of different iteration numbers to
approximate the optimal operation weights in DARTS's standard search space on CIFAR-10. 10. We conduct three parallel tests for each M and report the mean and stan- dard deviation of top-1 accuracy.
Iteration number
M=2
M=5
M=8
M=10
Error (%) STD
2.62
2.60
2.57
2.54
+0.15
#0.09
+0.03
#0.07
Params (M)
2.91
3.40
3.52
3.71
B.4 COMPARISION WITH PEER METHODS ON S1-S4
Unlike R-DARTS (Zela et al., 2020b) that constructs models by stacking 8 cells and inital chan- nels, SDARTS (Chen & Hsieh, 2020) builds models by stacking 20 cells and 36 initial channels. To compare with SDARTS for fair, we follow its settings and report our results in Table 7. Specifically, we conduct four parallel tests each benchmark by searching with different random seeds. Tabel reports the best and average performance report the best performance of four parallel tests. According to the results, observe ZARTS achieves state-of-thee thefthheart art on 7 benchmarks and SDARTS- slightly outperforms our ZARTS on 5 benchmarks.
our method. Note that other methods in Tabel 7 only
16

---

Under review as a conference paper at ICLR 2022
Non. Mlenntte
S-ABIS
ZARESS-GE GLD
ZARTS-GLD
120
75
100
175
Eporh
Epoch
(a) Trend of Number of Parameterless Operations (b) Trend of Number of Identity Operations Figure 5: Trends of number parameterless operations and identity operations in each normal cell searched by different NAS methods CIFAR-10 10 for 200 epochs. The parameterless operations include max pooling, average pooling, and identity operation.
B.5 CONVERGENCE ANALYSTS
The convergence ability of NAS methods describes whether search method can stably discover effective architectures along the search process. A robust and effective NAS method should be able to converge to exemplary architectures with high performance. This work follows Amended- DARTS (Bi et al., 2019) and evaluates the convergence ability by searching for an extended period (200 epochs). However, since it is time-consuming train every derived architecture along the search process, we illustrate the trend of number of parameterless operations (pooling and iden- tity operations) in each normal cell represent the performance of architectures (Fig. 5). Recent works (Chen et al., 2019; Bi ct al., 2019; Zela et al., 2020b) show that architecture with more than parameterless operations (especially identity operations) usually has a bad performance, which is typical phenomenon of the instability issue. Here, we show the number of parameterless operations of our ZARTS Fig. 5 and compare with another three methods, including DARTS, PC-DARTS and S-DARTS. We observe that the architectures discovered by DARTS, PC-DARTS and S-DARTS will be gradually dominated by parameterless operations (especially identity operation), implying that the instability issue occurs. In contrast, ZARTS can stably control the number of parame- terless operations.
B.6 VISUALIZATION OF ARCHITECTURES
Note that in all our experiments, we directly utilize the architecture at the final epoch (epoch 50) as the inferred network. No model selection procedure is needed.
We visualize the architectures of normal and reduction cells searched by ZARTS in DARTS's search space on CIFAR-10, 10, is shown in Fig. 6. The architecture searched on CIFAR-100 dataset is illus- trated in Fig. 7. We also conduct experiments in the four difficult search spaces of RDARTS (Zela al.. 2020a) on CIFAR-10 (Krizhevsky et al., 2009), CIFAR- 100 (Krizhevsky et al., 2009), and SVHN (Netzer et al., 201 1). The searched architectures are illustrated in Fig. 8, Fig. 9, and Fig. 10.
K0,00 363
Der 301
dbLoveas
Recon Dtt, MULeEE 343
PIL.VE 303
(a) The normal cell searched by ZARTS
(b) The reduction cell searched by ZARTS
Figure 6: The architectures of normal and reduction cell searched by ZARTS on CIFAR-10 in DARTS's search space. Model constructed by the above cells achieves 97.54% accuracy on the CIEAR- 10 dataset with 3.5M parameters.
17

---

Under review as a conference paper at ICLR 2022
up
spp cem 1s
[el]
Mp comr
scppccomes
hp
3k3
pool 303
Akp_zoweee
16-2
pool Sel
(a) The normal cell searched by ZARTS
(b) The reduction cell searched by ZARTS
Figure 7: The architectures normal and reduction cell searched by ZARTS on CIFAR-100 in DARTS's search space. Model constructed by the above cells achieves 84.54% accuracy the CIFAR- 100 dataset with 4.0M parameters.
TIXX poot 363
Als CEASI
20
4.18]
mon
scpL 333
(a)
(b)
Je3
(c) S3
c_(k22
squamm
cune 1-
1g
uqp mmy
sep com. 3x3
S4
Figure 8: The architectures of normal and reduction cells searched by ZARTS on CIFAR-10 in the four difficult search space of RDARTS. The left column shows the normal cells, while the right column shows the reduction cells.
18

---

Under review as a conference paper at ICLR 2022
maa
[1-2]
153
m13 200.
prol 3d
dil 558
pood 363
(a) SI
sep cuny 3,3
(K-2)
sep. conv.
Sep conn
scp_cmn__M 33
comv 3x3
[K-1]
spuam 363
skip_comest
stip
c_
coow
conv. 3x3
(kkk]
(k-2)
sep.
skip ponmen
(b)
squa 3x3
skip conteii
Scl
dep. comnect
c_kk] 11
10p 313
connet
sep com
(c) S3
6_lk 11
sop_coay 313
squ.mee 133
cotv 3X3
ces Ne
6 (b-2)
upp sopm
xp par
(d) S4
Figure 9: The architectures of normal and reduction cells searched by ZARTS on CIFAR-100 in the four difficult search space of RDARTS. The left column shows the normal cells, while the right column shows the reduction cells.
19

---

Under review as a conference paper at ICLR 2022
max poot 363
(B-3)
pool
skmpecomnett
max poo.pool
max pool 3xT
di
Sup coned
[--]]
sp cony
SI
dep comnect
HgL.mm, J63
onn J63
Skp
Aip
C1
Sitt 2d
Sp
(b) S2
comnec
[--2]
munsc
E.
comeect
coinech aep
ap.rew: 3r1
PLENE
skip cunnect
(c)
sep_comw_313
noise
[_
SOILEMEN .313
sop_comy
sop_ecev__ _363
sop_coax__133
181
cop.omm 33x3
[.lk]
Sep_couy 313
[k- sop_comy 3x3
noise
[K-1]
S42 App.nee 3-3
zuise
(d) S4
Figure 10: The architectures of normal and reduction cells searched by ZARTS SVHN in the four difficult search space of RDARTS. The left column shows the normal cells, while the right column shows the reduction cells.
20

---

Under review as a conference paper at ICLR 2022
Sp coIv 3x3
pool
dll cone 365
[k:]]
aap panr 3x3
c.13]
Din 355
egp oney Twy
pinp 3n3
(a) The normal cell derived at 10 epoch
(b) The normal cell derived at 15 epoch
(k:3)
ssp 363
(k)
max pool 3x
Su5
Sep OOWW
(c) The normal cell derived at epoch
(d) The normal cell derived at 25 epoch
Au
up
The and
Aup Can,
(e) The normal cell derived at epoch
(I) The normal cell derived at 75 epoch
di Lovey, Jdl
KR.yen 203
upucom
The normal cell derived 100 epoch
(h) The normal cell derived at 125 epoch
(i) The normal cell derived at 150 epoch
ji) The normal cell derived at 175 epoch
(k) The normal cell derived at 200 epoch Figure 11: The derived architectures of normal cell every 25 epochs, which are searched by ZARTS on CIFAR-10 for 200 epochs.
21

---

Under review as a conference paper at ICLR 2022
20p_000W .55
(
95p_s0me_5sS
kopusooo_333
max__ooo 3x3
CLINI
h-2]
(a) The reduction cell derived 10 epoch
(b) The reduction cell derived 15 epoch
1k:21 FaX max_ppa 3xd
dil
spp com.
2
WOLpee, 3r
R
[|
Slip conneet
ROPLANIRN 3+3
PRL.IOL 263
(c) The reduction cell derived at 20 epoch
(d) The reduction cell derived at 25 epoch
Ho
ynd 2
city JOw.E
(e) The reduction cell derived 50 epoch
(f) The reduction cell derived at 75 epoch
BlA pool 3x pool 3x3
[b-2]
maX pool 3x3
<kip connect
S_lkk
BIX pool
[b-]]
565
and
g The reduction cell derived at 100 epoch
(h) The reduction cell derived at 125 epoch
Fas and 263 P
Ang pvrl ong port
pook
201
parl Tes.
ii The reduction cell derived at 150 epoch
ii) The reduction cell derived at 175 epoch
diquneee
JUMI
peel Yox
XP WOP.EEROO
(k) The reduction cell derived 200 epoch
Figure 12: The derived architectures of reduction cell every 25 epochs, which are searched by ZARTS on CIFAR-10 for 200 epochs.
22


Reviews:
[{"review_id": "xc7HQgIFuQJ", "reviewer": "Reviewer_rwzN", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The empirical analyses are reasonable and sound. The proposal to use zero-order optimization methods is novel and interesting. The paper is well-written. I mainly have the following concerns.\n\n1.\tSince the authors use zero-order methods to optimize the architecture parameters, there is no requirement that the loss is differentiable wrt the architecture parameters. In this case, can we optimize the binary architecture parameters directly without the need to introduce the continuous softmax relaxation? \n2.\tThe zero-order optimization methods introduce much more computational cost than the first-order gradient-based method, which causes the high search cost. So, it would be difficult to directly search on ImageNet. Considering many NAS methods have already been able to directly search on ImageNet, this drawback limits the potential applicability of the proposed methods.  \n3.\tI think the stability of a NAS method can be claimed only when the method is able to produce similar searc results stably. Can the authors prove that multiple implementations of the proposed search method would lead to the same architecture or similar architectures with close performances? The result of Figure 2 is interesting. But I think the trends in Figure 2 are of randomness and difficult to reproduce. It is better to report the averaged trends of multiple implementations.  \n4.\tThe search results are not significantly better than some baselines. On ImageNet, the result is not better than PC-DARTS (ImageNet) that has 24.2% err. as reported in [1]. Besides, many studies are not cited and compared with, such as [2,3,4,5]. \n5.\tIs the proposed method applicable to the chain-based search space adopted in [6,7,8]? \n\n\n[1] Xu et al., PC-DARTS: PARTIAL CHANNEL CONNECTIONS FOR MEMORY-EFFICIENT ARCHITECTURE SEARCH\n\n[2] Liang et al., DARTS+: Improved Differentiable Architecture Search with Early Stopping\n\n[3] Chu et al., DARTS-: ROBUSTLY STEPPING OUT OF PERFORMANCE COLLAPSE WITHOUT INDICATORS\n\n[4] Yang et al., ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding\n\n[5] Zhou et al., Theory-Inspired Path-Regularized Differential Network Architecture Search\n\n[6] Chu et al., FairNAS: Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search\n\n[7] Yu et al., BigNAS: Scaling up Neural Architecture Search with Big Single-stage Models\n\n[8] Mei et al., AtomNAS: FineGrained End-to-End Neural Architecture Search\n", "summary_of_the_paper": "This study proposes to use zero-order optimization methods for neural architecture search based on the empirical observation that the approximation of differentiability will distort the loss landscape and lead to the biased objective and inaccurate gradient. Experiments on multiple datasets are conducted to show the improved stability and performance of the search results. ", "summary_of_the_review": "I vote for a weak accept currently considering the novelty of the proposed methods. But the concerns above need to be well addressed. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "qRwTiG-fnyk", "reviewer": "Reviewer_JSTM", "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": "The instability of DARTS has always been an topic in the NAS area, and has drawn a lot of attention. Many works have investigated the issue and propose methods to alleviate it.\n\nThis paper, conducts analysis on the first/second order approximation of network weights and points out that such approximation leads to the instable optimization of architecture parameters. Consequently it proposes to solve the problem via zero-order optimization, and propose three zero-order optimization methods, which is very novel. Experiments demonstrate the effectiveness of the proposed methods.\n\nThe weakness:\n1. The increased search cost due to the sampling and estimation process.\n2. Though the experimental results improve against original DARTS, however these tasks are explored by plenty of works and an error rate of around 2.50 and 24.3 on CIFAR-10 and ImageNet are achieved by many works and are not that outstanding. More experiments may strengthen the results.\n\nSome questions for the authors:\n1. In ZARTS-GLD, it seems that the network weight $w^{*}$ is estimated by the current weight $w$ and the method searches within a small area around current architecture parameter $\\alpha$. Is this estimation accurate and why?\n2. In section 5.1, convergence analysis, do the architectures derived every 25 epochs change or do they keep the same after several epochs?\n\nOverall, I think this is a good work.", "summary_of_the_paper": "This paper presents ZARTS, a zero-order optimization method for DARTS, to search without enforcing the approximation of the network weights. It conducts in-depth analysis on the first/second order approximation in DARTS, and points out that such approximation leads to bias and instability. Then the work proposes three zero-order optimization methods to solve the issue.", "summary_of_the_review": "This work presents zero-order optimization methods for DARTS, which is very novel in the area. The paper is well-organized, with sufficient analysis and sound technical contribution. I think it is a good work.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Xt-5yXniZNb", "reviewer": "Reviewer_5Kkb", "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 analysis of how first-order optimization sharpens the landscape of loss (fig 1) is interesting. It sheds some lights on why first-order DARTS faces the problem of instability during the search. \n++ The paper is the first to apply zero-order optimization methods to solve NAS, which could open a new research direction of NAS.\n++ The analysis on connecting ZARTS and DARTS provides a theoretical explanation on why ZARTS can work better than DARTS.\n++ The experiments are extensive and can demonstrate the effectiveness of the proposed ZARTS.\n\nCons\n-- The three zero-order optimization methods are all proposed by other works, which weakens the novelty of this paper.\n-- The search costs of ZARTS are not appealing comparing to other differentiable NAS methods like P-DARTS or FairDARTS (Table 4). Moreover, the top-1 error rate of ZARTS is similar to that of P-DARTS, while being slower at search.\n- The superiority of ZARTS is not obvious in Table 7 comparing to SDARTS.", "summary_of_the_paper": "This paper (ZARTS) proposes to apply gradient-estimation-based zero-order optimization methods to tackle neural architecture search (NAS). Two major contributions are made by this paper: (1) it is the first to borrow the methods of zero-order optimization to solve NAS  problem; (2) it shows that zero-order optimization methods can greatly avoid the training instability of first- or second-order optimization NAS methods like DARTS (which sharpens the loss landscape). Moreover, this paper also provides an explanation on how ZARTS is connected with DARTS. Extensive experiments demonstrate the efficacy of ZARTS.", "summary_of_the_review": "Overall, it is a good paper that opens a new research direction of differentiable NAS family. The quality in terms of visualization, theoretical proof and empirical evaluation are also good. So, I recommend an 'accept' for this paper. The concern preventing me from giving higher rating is that all the optimization methods are directly obtained from previous works.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a series of zeroth order optimization approaches to stabilize DARTS training. Although the reviewers think that zeroth order approach is novel to the NAS community, they also point out several weaknesses. In particular, the method will introduce extra computation time and the results are not really standing out comparing with other state-of-the-art methods. Therefore, despite some interesting ideas are presented in the paper, we decide to reject the paper and encourage the authors to address those weaknesses in their future revision.
Decision: Reject