ZARTS: On Zero-order Optimization for Neural Architecture Search
Authors: Xiaoxing Wang
Wenxuan Guo
Jianlin Su
Xiaokang Yang
Junchi Yan
Venue: NeurIPS 2022 Accept (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 often distorts 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. Finally, we combine our ZARTS with three orthogonal variants of DARTS for faster search speed and better performance.  Source code will be made publicly available at:  \url{https://github.com/vicFigure/ZARTS}.

ZARTS: On Zero-order Optimization for Neural Architecture Search
Xiaoxing Wang', Wenxuan , Su², Xiaokang Yang', Junchi Yan
DDeparmeent of Computer Science and Engineering, Shanghai Jiao Tong University
Shennhen Zhuiyi Technology Co., Ltd.
(figurei_wwe _xpeee__xxxeeee arya_g ar xkyangg yanjunchi] @ ed..tu.uucc
bojonesu@xezhuiyy.ccm
Abstract
Differentiable architecture search (DARTS) has been a popular one-shot paradigm for NAS due to its high efficiency. It introduces trainable architecture parameters represent the importance of candidate operations and proposes first/sccond- 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 often distorts 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, 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 the gradient descent algorithm and show that our ZARTS can be seen as a robust gradient-free counterpart DARTS. Extensive experiments and search spaces show the remarkable performance of our method. In particular, results 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 discovered architecture achieves 97.54% accuracy on CIFAR- 10 and 75.7% top- accuracy on ImageNet. Finally, we combine our ZARTS with three orthogonal variants of DARTS for faster search speed and better performance. Source code will be made publicly available https:: / www.sthb....m.iii.t.et
multiple datasets
Introduction
It remains open to search for efficient architectures automatically instead of by humans 27 14 [5] Neural architecture search (NAS) has attracted wide attention, which can be modeled as bi-level optimization for network architectures and operation weights. One-shot NAS [ is popular search framework that regards neural architectures directed acyclic graphs (DAG) and constructs supernet with all possible connections and operations in the search space. DARTS (20) further introduces trainable architecture parameters to represent the importance of candidate operations, which are alternately trained by SGD optimizer along with network weights. It proposes first-order approximation to estimate the gradients architecture parameters, which is biased and may lead to the severe instability issue shown by (3). Other works 388 6 point out that architecture parameters will converge to sharp local minimum resulting in the instability issue, so they introduce extra regularization items making architecture parameters converge to flat local minimum.
"The SJTU authors are also with MoE Key Lab Artificial Intelligence, SJTU, Junchi Yan the corre- sponding author who is also with Shanghai Al Laboratory.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we empirically show that the first-order approximation of optimal network weights sharpens the loss landscape and results in the instabilitty issue of DARTS. also shifts the global min- imum, misleading the training of architecture parameters. To this end, we discard such approximation and turn to zero-order optimization algorithms, which can 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 a large margin and can discover efficient architectures stably multiple public benchmarks. This paper sheds light the frontier of NAS by:
Establishing zero-order based robust paradigm solve bi-level optimization for NAS. Dif- ferentiable architecture search has been well-developed area [2] 34 31] 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, as shown in Fig. [ (a) and (b). To this end, we propose a flexible zero-order optimization NAS framework to solve the bi-level optimization problem, which is compatible with multiple potential gradient-free 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 implementations of ZARTS can be seen as gradient-fie frree counterparts to DARTS, being more stable and robust.
3) Strong empirical performance and robustness. Experiments on four datasets and five search spaces show that, unlike DARTS, which suffers the severe instability issue [88 31 ZARTS can stably discover effective architectures various benchmarks. In particular, the searched architecture achieves 75.7% top-1 accuracy on ImageNet, outperforming DARTS and most of its variants. Also, our ZARTS can be further improved by combining with orthogonal DARTS variants, achieving 97.81 % on CIFAR-10 after searching in 0.5 GPU-day.
2 Related Work
One-shot Neural Architecture Search. 1 constructs a supernet and all candidate architectures can be seen as its sub-graph. DARTS (20) introduces architecture parameters to represent the importance of operations in the supernet and update them by gradient descent. Some works 31 I0 reduce the memory requirement in the search process. While [38 6 point out the instability of DARTS, i.e., skip-connection gradually dominates the normal cells, leading to performance collapse during search.
Bi-level Optimization for NAS. NAS can be modeled as a bi-level optimization for architecture parameters and network weights. DARTS (20] proposes the first/second-order approximations to estimate gradients of architecture parameters so that they can be trained by gradient descent. However, we show that such an approximation will distort the loss landscape and mislead the training of architecture parameters. architecture parameters that require the Hessian inverse of network weights, which is even unfeasible to compute. This work discards the approximation in DARTS and attempts to solve the bi-level optimization by gradient-fre free algorithms.
Mmended-DARTS [3] derives an analytic formula of the gradients w.r.t.
Unlike gradient-basee optimization methods that require the objective differentiable w.r.t. the parameters, zero-order optimization can train parameters when the gradient is unavailable or difficult to obtain, which has been widely used in adversarial robustness for neural networks (5] [6]. meta learning (28). and transfer learning 29 22 aim at AutoML and utilize zero-order optimization to discover optimal configurations for ML pipelines. In this work (to our best knowledge), we make the first attempt to apply zero-order optimization NAS and experiment with multiple algorithms, from vanilla random search [TT] to more ad advanced and effective direct search [2), showing its great superiority against gradient- based methods.
Zero-order Optimization.
3 Bi-level Optimization in DARTS
Following one-shot NAS 11. DARTS constructs supernet stacked by normal and reduced cells. Cells in the supernet are denoted by directed acyelic graphs (DAG) with N nodes [ which represents latent feature maps. Each edge ei,j contains multiple operations {oi,, E O}, whose
2

---

100
1.00
DARIS
ZARTS-MEI
ZARTS-GLD
0.20
00.00.0723
-022
-0.2
-50
-120
(a) Landscupe w.r.t.c with wist
(b) Landscape w.r.t. a with w (c) Tracks of optimization path
Figure I: Loss landscapes w.r.t. architecture parameters a where the red star indicates the global minimum. (a) the landscape with wist (b) the landscape with w", which is obtained by training w for 10 iterations. To fairly compare the landscapes in (a) and (b), we utilize the same model and candidate a points. The first-order approximation sharpens the landscape. (c) displays the path of DARTS and ZARTS. Starting at the same initial point, ZARTS converges to the global minimum.
importance is represented by architecture parameters ag Therefore, NAS be modeled bi-level optimization problem by alternately updating the operation weights w (parameters within candidate operations each edge) and the architecture parameters
min weal( (a). a), s.t. (a(a) = arg min Ctrain(war Q
3.1 Fundamental Limitations in DARTS
By enforcing an unverified (and in fact difficult to verify) assumption that the search loss Leal (ax), a) is differentiable w.r.. a, DARTS (20] proposes second-order approximation for the optimal weights w" (ax by applying one-step gradient descent:
(2) where& & is the learning rate to update network weights. Thus the gradient of the loss w.r.t. a, VaLrallw" (a), a)), can be computed by the chain rule: VaLval(w"(ay a) = VaLual a) VVà Ctran (w, Ver Leal (w', (w', a). Nevertheless. the second-order partial derivative is hard to compute, so the authors adopt the difference method, which is proved in the appendix.
w w'(a) R (an w - <V w Ltrain
For efficiency, first-order approximation is introduced by assuming w (a:) being independent of a, as shown in Eq. which much faster and widely used in many variants of DARTS 7 31 38)
w R (e) w.
The gradient is then simplified as: TaCoail"" (a), = V Loatea a)), which exacerbates the estimation bias. Reexamining the definition of w (xx in Eq. one would note that it is intractable to derive mathematical expression for w" (ar), making Lvol (w (a)),, a) even non-differentiable w.r.t. a. Yet DARTS has to compromise with such approximations as Eq. and Eq, 3 so that differentiability is established, and SGD can be applied. However, such sketchy estimation of optimal operation weights can distort the loss landscape w.r.t. architecture parameters and thus mislead the search procedure, shown in Fig. T and analyzed in the next section.
3.2 Distorted Landscape and Biased Optimization
Fig. T fillustrates the loss landscape with perturbations on architecture parameters a, showing how different approximations of wt affect the search process. We train supernet for 50 epochs and randomly select two orthonormal vectors as the directions to perturb a. The same group of pertur- bation directions is used to draw landscapes in Fig. [ a and (b) for fair comparison. Fig. Ia) shows the loss landscape with the first-order approximation in DARTS, (a)) = w, while Fig. T(b) shows the loss landscape with more accurate w' (ox), which is obtained by fine-tuning the network weights w for 10 iterations for each a. Landscapes (contours) are plotted by evaluating L at grid points ranging from -1 to 1 at interval of 0.02 in both directions. Global minima marked with stars on the landscapes, from which we have two observations: 1) The approximation wise = w shifts the global minimum and sharpens the landscape which is the representative characteristic of
A "sharp" landscape has denser contours than "flat" one.

---

Algorithm ZARTS:
Zero-order Optimization Framework for Architecture Search
Hyper-parameters: Operation weights w, architecture parameters a, sampling number N, iteration number M, update estimation function ((.).
repeat
Sample candidates: {u: and get a = atu, Estimate optimal operation weights
("(x,) by descending Vw (w, ax)) for M iterations;
Get update direction: u = o (fu w (a
Update architecture parameters:
aut
until Converged
The sampling strategies and update estimation functions o(-) for three different zero-order optimization algorithms are detailed in Table
instability issue pointed out by 38 2) Accurate estimation for w" leads to flatter landscape, indicating that the instability issue can be alleviated. Moreover, we display the landscape with second-order approximation Wind in the appendix, which is also sharp but slightly flatter than Fig. T (a). Consequently, we discard the first/second-rrde approximation in DARTS and instead use more accurate w coordinated with zero-order optimization.
Fig. (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 random point, update architecture parameters a for ten iterations by DARTS and ZARTS, and draw the optimization path. ZARTS gradually converge to the global minimum, while DARTS fails.
4 Zero-order Optimization for NAS
This paper goes beyond the Ist/2nd-order approximation in DARTS and proposes to train architecture parameters by zero-order optimization, allowing for more accurate estimation for w wa(a). Alg. 1
outlines the generic form of our ZARTS framework. We adopt three representative techniques:
vanilla zero-order optimizer, random search (RS) [21], and advanced algorithms: Maximum- likelihood Guided Parameter Search (MGS) 32 and Gradientl Less Descent (GLD) 112, presented
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 denote L(xx) & (wo (ax),, a)) as the objective w.r.t. architecture parameters a E Rd (Eq. 1.. and C(a + u) & Lval (w u), u), where u is the update for a.
in Sec. 4. 4.2 4.3
preliminaries. Further,
4.1 Optimizer I: ZARTS-RS
We adopt Multi-point estimator, shown in Table 1 baseline of our ZARTS:
(dd)
N
VaL(a)= = 2pN
IC(a + mus)) - L(a - jau:)] u;
(4)
where u ~ q sampled from spherically symmetric distribution 4, 0 is smoothing parameter, and (pd) is a dimension-depender factor related to q. Specifically, sed) = 1 when is a standard normal distribution // (V, I), and (dd) = when q is a uniform distribution on a unit sphere Sd-1,
4.2 Optimizer II: ZARTS-MGS
eokiimum-likelibne guided parameter search (MGS) is an advanced zero-order optimization al- gorithm for machine translation (32). We attempt to apply to the NAS task. We first define distribution for the update of architecture parameters, u. as follows:
C(a u) -(aa) -
p(ula:) ((ax) Z(a:)
p(ula)
exp
(S)
where p(u(a) = exp (-[C(a +) (T) is an unnormalized exponential distribution, and ((a) = ( a du is its normalization coefficient. temperature parameter controlling the variance of the distribution.

---

Table 1: Configuration of three methods used in the ZARTS scheme. The main difference lies in the meaning of function ( RS follows the traditional gradient estimation algorithms, MGS estimates the update according to the improvement in the loss function, while GLD uses direct search. Note that the ZARTS framework general and can support more configurations besides those listed.
Algorithm
Sampling strategy
Update estimation function (u,, w (ar))
ZARTS-RS
u, g(u(a). any spherically symmetric distribution.
vidd 2pr
>>=
[C(a + joi)) L(a ymu,] u, (Eq.
g(ujar), any proposal distribution.
ZARTS-MGS
Zau, > Aayyln)
(Bq.88)
0. 8--1 uniform distribu- tion unit sphere.
ZARIS-GLD
u' arg min; (C(á) a u: (Eq. 10
Intuitively, with higher probability contributes more to the objective. Hence, the optimal update of architecture parameters can be estimated by u* Eu-p(ula)) [u]. However, since the probability p(u(a) is an implicit function relying L(a u), making it impractical to obtain the expectation, we refer to [32] and apply importance sampling to sample from proposal distribution g(u(a) with known probability function:
u = =uu-p(uja = p(ula)
/ (ulaa))
p(ula)
udu
u du [(a)q(ua)
Z(a)
p(ula)
N
p( a3)
-uuag(ula)
2
0", (6)
(ua))
N
Z(a))q(u,ee
where {u:}a N are sampled from the proposal distribution q(u()). Similarly, the normalization coefficient ((a) can be computed as follows:
Z(a)= f p(ula)du 1
p a (u a)
For convenience, we define a ratio representing the weight on each sample as a(laa) optimal update for architecture parameters in Eq. 66 can be computed by:
((laa) qu)ax)
The
expíí - -llaatut--aaaa'))
ā(u:la) Σド= Au
Σ
exp [C L(a))
U,
(
Finally, the architecture parameters updated by n' Importance sampling diagnostics are conducted to verify the effectiveness of ZARTS-MGS (in the appendix).
4.3 Optimizer III: ZARTS-GLD
Unlike the above two algorithms that estimate gradient or the update for a. 12 propose the so-called GradientLess Descent (GLD) algorithm, which falls into the category of truly gradient-free (or direct search) methods. The authors provide theoretical proof of the efficacy and efficiency of the GLD algorithm and suggestions on the choice search radius boundaries. Specifically, they prove that the distance between the optimal minimum and the solution given by GLD is bounded and positively correlated with the condition number of the objective, where the condition number Q is defined as:
L[a A) [(a)) ||||| |A [(a)]
max ISiCK
(9)
The loss landscape in Fig. (b) pretty flat, implying a low condition number, thus the high efficiency of ZARTS GLD. Specifically, at each iteration, with predefined search radius boundary [r. R), we independently sample candidate updates } for architecture parameters on spheres with various radii (2-* log((/r)) and perform function evaluation at these points. By comparing L(a:) and {L(a + u.)). a steps to the point with minimum value, or stay the current point if none of them makes an improvement. The architecture parameters are then updated by +- + u".
u' arg min ( a, & a a+
(10)
5

---

4.4 Connection between DARTS and ZARTS
The similarity between tradient-estimation based zero-order optimization and SGD builds an essen- tial connection when the objective function is differentiable. For ZARTS-RS. RS,, we adopt multi-point estimator to approximate the gradient with limited bound [23 2). Details are put in the supple- mentary material. Therefore, ZARTS-RS degenerates to second-order DARTS if L(a)) is indeed differentiable w.r.f a and the iteration number M is set to
Next, we theoretically show that MGS [32 degenerates to the gradient descent algorithm by using first-order Taylor approximation. Then we analyze the relation between ZARTS-MGS and DARTS.
Proposition 1. When L(x) in Eq. is differentiable w.r.t. a, MGS algorithm [32] degenerates SGD (used in vanilla DARTS) by the first-order Taylor approximation for L(a)), i.e., u x - Vaf(a).
Proof. Denote g A V ((x)) as the gradient of L. The Taylor series of L at a up to the first order gives C(a + u) - ((x)) = u.g. Applying it to p(ula) in Eq. 5 yields:
g/r (gg
p(ula)
Z(g)
e- u g/7 du.
(11)
Since ||u|| is constrained within E to make sure the rationality of first-order Taylor approximation, the optimal update u* then becomes:
u' Siuis u.e u g/T du
VgZ(g) (Z(agg)
--v - Z(g).
(12)
Z(g)
Note that u g -||u|||| |clos,, where 7) is the angle between and g. According to the symmetry of integral, (g) is determined once ||g|| is given. We formulate (gg) as ((lg)) with the chain rule:
u = - In 2(g) = - -v In ((lgg) = V g ((1gg) ((g)))
ViRi Z(lggl)
V Igll =
(13)
T Z [g
Since 2(1gg]). V [gll Z ((( ||l|| are all scalars, we have
u x - VaC(a) = -aaauuul
(14)
That is, the optimal update u in MGS algorithm shares a common direction with the negative gradient- - ((.((a), used by gradient descent.
n
Based on Proposition 1 ZARTS-MGS 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 diffcrentiability assumption.
However, unlike DARTS, which has to estimate w' (ax) by wist or Wind to satisfy the differentiablity property of Leal and update a by gradient descent algorithm, ZARTS, without such assumptions, can compute w² (ax) by training network weights w for arbitrary numbers of iterations, leading to more robust and effective training for architecture parameters, as shown in the next section.
4.5 Variants and Speedup of ZARTS
ZARTS can be flexibly and seamlessly combined with variants of DARTS for boosting as it can be seen as expansion of DARTS as analyzed in section 4.4 Here, we derive three variants of ZARTS by combining it with prior works: P-ZARTS based on P-DARTS 77. GZAS based on GDAS [TO), and MergeZARTS based MergeNAS (3I] Implementation details illustrated in the appendix. These variants can speed up ZARTS twice and reduce the search cost to 0.5 GPU-day. Moreover, GZAS and MergeZARTS also reduce the GPU memory cost during the search process.
The performance of these variants is reported in Table
5 Experiments
We first verify the stability ZARTS (with three zero-order optimization methods RS, MGS, GLD) on the four popular search spaces of R-DARTS (38) on three datasets including CIFAR-10 [17).

---

Table 3:
Performance CIFAR. The top reports the accuracy of the best model. The bottom gives Reported by [0]] by B8]
the mean of four independent searches as used by [8 6 37
Params (M) L
Error
Cost
Params (M)
Error
Cost (GPU-days) 4
CIFAR-10
CIFAR-100
(S6 4
(GPU-days)
(%) 4
DARTS (lst)
20
3.3
3.00
AmocbaNet
3.1
18.93
3150
DARTS (2n)
20
3.4
2.76
PNAS 10
3.2
19.53
150
best
P-DARTS 7
3,4
2.50
0.3
ENAS 25
4,6
19.43*
0.45
ISTA-NAS 30
3.3
2.54
0.05
P-DARTS
17.49
0.3
PR-DARTS
2.32
GDAS 10
3,4
18.38
0.2
DARTS- 3
3.5
2.50
ROME 3D
4,4
17.33
0.3
ZARTS (ours)
3.5
2.46
1,0
PR-DARTS
0.17
DARTS
8
3.4
17.16
0.4
(ARTS((st) 37
3.38:40.23
ZARTS (ours)
4.0
15.46
1.0
SGAS (Cri.) 18]
3,9
2.67:0.21
R-DARTS 88
2.95+10.21
1.6
DARTS
20
20.58:10.44
0,4
SDARTS-ADV
6
3,3
2.61 10002
1.3
R-DARTS
18
18.01
1.6
Amended-DARTS
3
3.3
2.71
1.7
ROME
30
4.4
17.41=0.112
0.3
DARTS-
3.5
2.59:10.08
DARTS-
3.3
17.51
0.4
ZARTS (ours)
3.7:10.3
2.54
1.0
ZARTS (ours)
4.1
16.29:10.53
1.0
CIFAR-100 [7], and SVHN 24 We then follow Mmeeded-DARTIE and empirically evaluate the convergence ability of our method by searching for 200 epochs. Performance trends of the discovered architectures are drawn in Fig. [(a] Next, we compare with the peer methods on the search space of DARTS 20 to show the efficacy of our method. Finally, we derive three variants of ZARTS with faster search speed by combining ZARTS with the variants DARTS, showing the flexibility and potential of our ZARTS framework. All the experiments are conducted on NVIDIA 2080Ti. The details of search spaces and experiment settings are given in the appendix.
5.1 Stability Evaluation
The instability of DARTS has drawn recent attention. Amended- DARTS shows that skip- connection gradually dominates the discovered architectures after searching by DARTS for 200 epochs. R-DARTS (38) proposes four search spaces, S1-S4, which amplify the instability of DARTS, as such dom- inance occurs after only 50 epochs of searching. These studies expose the instability of gradient-basee based methods.
Table 2: Test error (%) with DARTS and its variants on S1- S4 search spaces, on CIFAR- 100-10011000 and SVHN. We adopt the same settings R-DARTS 39) The best and second best are underlined in boldface and boldface, respectively.
R-DARTS
DARTS
ZARTS (ours)
DARTS
DP
L22
ES
ADA
RS
MGS
GLD
S1
3.84
3.11
2.78
3,01
3.10
2.83
2.65
2.50
2
S2
4.85
3.48
3.31
3.26
3.35
3.35
3.24
3.08
S3
3.34
2.93
2.51
2.74
2.59
2.59
2.56
2.56
C S4
7.20
3.58
3.56
3.71
4.84
4.90
3.70
3.52
SVHI CIFAR- 100
S1
29.46
25.93
24.25
28.37
24.03
23.64
23.16
23.33
To verify the stability of our method,
S2
26.05
22.30
22.24
23.25
23.52
21.54
20.91
21.13
we search on S1-S4 proposed by R-DARTS and conduct convergence analysis following Amended Amended-DARTSS
S3
28.90
22.36
23.99
23.73
23.37
22.62
22.33
21.90
S4
22.85
22.18
21.94
21.26
23.20
23.33
21.31
21.00
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
Performance on S1-S4. We first
83
3.41
2.49
2.48
2.50
2.50
2.41
2.52
2.44
search on the four spaces on CIFAR- 10, CIFAR- and SVHN. The eval-
S4
3.05
2.61
2.50
2.51
2.46
2.59
2.48
2.53
Specifically, four tests are conducted each We observe that ZARTS achieves outstand- ing performance with great robustness on 12 benchmarks. All three zero-order algorithms outperform DARTS notably. Even the vanilla zero-order algorithm ZARTS-RS RSS achieves similar robust perfor- mance as R-DARTS, which verifies our analysis in Fig. i.e.. the coarse estimation wi.e in DARTS distorts the landscape and causes instability. Though ZARTS-GLD performs best in Table 2 it falls into the category of direct search methods, requiring more sampling for candidate updates u and thus more search cost (2.2 GPU-days on the search space of DARTS) than ZARTS-MGG (1.0 GPU-days). ZARTS-MGS is chosen by default if not otherwise specified, for its cost-effectiveness.
uation settings are the same as R-DARTS benchmark, among which the best is reported in Table 2
338
Convergence Analysis. The convergence ability of NAS methods describes whether search method can stably discover effective architectures along the search process, i.c., whether the discovered
7

---

97.6
4.5
Num of Parameters (M))
4.0
Top-1 Accuraly
3.0
2.5
DARTS
DARTS
100
125 Epoch
150
125
150
175
Epoch
(a) Trend of T accuracy
(b) Trend 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.
architectures' ultimate performance (top-1 accuracy) can converge a high value. Amended- DARTS [3] empirically shows that DARTS has poor convergence ability: accuracy of the supernet increases but the ultimate performance of the searched network drops. Following -AnedS we run ZARTS and DARTS for 200 epochs and show the trend of performance and number of parameters 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 discovered by ZARTS perform stably well (around 97, .00% accuracy), while the performance of networks found by DARTS gradually drops. Moreover, the parameter number of networks searched by DARTS decreases significantly after 50 epochs, indicating that parameterless operations dominate the topology and the instability issue (39 occurs. On the contrary. ZARTS consistently discovers effective networks with about 4.0M parameters, showing the remarkable stability of our method. More details and visualization of architectures are shown in the appendix.
5.2 Performance on the Search Space of DARTS
Results on CIFAR. 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 re- ported in Table 3 In particular, ZARTS achieves 97.46% aver- age accuracy and 97.54% best accuracy on CIFAR-10, 10, outper- forming DARTS and its variants. Also, compared with Amended- DARTS that approximates opti- mal operation weights w" (a) by Hessian matrix, our method can stably discover effective architec- tures in fewer GPU days. More- over, Table 3 shows our method achieves 83.71 5% and 84.54% for mean and best accuracy (i.c., error%), on CIFAR- 100, outper- forming the compared methods by more than 1 1%.
Table 4: Performance ImageNet in DARTS's search space by two architectures. t direct search on ImageNet.
FLOPs Params Top-1 Err.
Cost (GPU-days) |
Models
(M) J
(M) |
(%) |
AmoebaNet A 26
555
5.1
25.5
3150
NASNet-A 41
564
5.3
26.0
1800
PNAS [T9
588
5.1
25.8
225
DARTS (2nd)
574
26.7
P-DARTS 7
557
4.9
24.4
0.3
PC-DARTS 35
586
5.3
25.1
0.1
FairDARTS-B
541
4.8
24.9
0.4
SNAS 33
522
4.3
27.3
1.5
GDAS 10
26.0
SPOS 13
323
3.5
25.6
12
ProxylesNNAS
24.9
Amended-DART'S
586
5.2
24.7
1.7
ZARTS (5.6M params)
647
5.6
24.3
1.0
ZARTS (5.0M params)
573
24.5
Results on ImageNet. For the transferability test, we follow the settings of DARTS transfer the network discovered on CIFAR- 10 to ImageNet. Models are constructed by stacking 14 cells with 48 initial channels. We train 250 epochs with a batch size of 1024 by SGD with a momentum of 0.9 and base learning rate of 0.5. We utilize the same data pre- pre-processing strategies and auxiliary classifiers as DARTS. Table shows the performance of our searched networks. ZARTS (5.6M) has 5.6M parameters and achieves 75.7% top-1 accuracy on the validation set of ImageNet, and ZARTS (5.0M) has 5.0M parameters and achieves 75.5% accuracy. Their structure details are given in the appendix, which has fewer skip connection operations than DARTS.

---

5.3 Variants and Speedup of ZARTS
The results of three variants of ZARTS, including the best and mean performance among four independent searches, are illustrated in Table [ We search for 50 epochs by each variant and train the discovered ar- chitectures for 600 epochs. The search and evaluation settings are in- troduced in the appendix. Specifically, GZAS outperforms GDAS by 0.3% with similar search cost, only 0.3 GPU-day. P-ZARTS outperforms P- DARTS by 0.15% and even surpasses ZARTS due to the handcrafted crite- ria in P-DARTS: setting the number of skip connection operations as 2. MergeZARTS achieves state-of- state-of-the- art performance with low search cost (0.5 GPU-day). We analyze that the weight merge technique among con- volutions in MergeNAS reduces the redundant network weights which alleviates the training difficulty for supernet and thus makes w" (a) more accurate after iterations of gradient descent.
Table 5: We derive the variants of ZARTS by combining ZARTS with the variants of DARTS, Experiments are con- ducted on CIFAR-IO. DARTS, GDAS, and P-DARTS report the best performance in their papers, and MergeNAS reports the average performance.
Params
Error
Cost (GPU-days)
Memory (GB) J
Models
(M)
(%)
DARTS (1st)
20
3.3
3.00
0.4
9.4
DARTS (2nd)
A0
3,4
2.76
1.0
9.4
ZARTS-best (ours)
3,5
2.46
1.0
9.4
ZARTS-avg. (ours)
3.7.0.33
0.54
1.0
9.4
GDAS [0]
3.4
2.93
0.2
3.1
GZAS-best (ours)
3.7
2.58
0.3
3.1
GZAS-avg. (ours)
3.5
2.66
0.3
3.1
P.DARTS P-ZARTS-best (ours)
3.4
2.50
0.3
3,5
2.30
0.4
9.4
P-ZARTS-avg. (ours)
3.3+
2.41=00155
0.4
9.4
MergeNAS (1st 31
2.9
2.73++0.02
0.2
4.4
MergeNAS (2nd) 31
2.9
2.68:10.01
0.6
4.4
MergeZ.ARTS- (ours)
4.0
2.19
0.5
MergeZ.ARTS-avg. (ours)
3.8++0.22.36
0.5
4.4
Conclusion and Future Work
DARTS has been a dominant paradigm in NAS, while its instability issue has received increasing attention 3 38 6). In this work, we have empirically shown that the instability issue results from the first-order approximation for optimal network weights and the optimization gap in DARTS, which is also raised in the recent study [3]. To step out of such bottleneck, this work proposes robust search framework named ZARTS, allowing for higher-order approximation for w" (ax) and supporting multiple combinations of zero-order optimization algorithms. Specifically, we adopt three representative methods for experiments and reveal the connection between ZARTS and DARTS. Extensive experiments on various benchmarks show the effectiveness and robustness of ZARTS. To our best knowledge, this is the first work that applies zero-order optimization to one-shot NAS, providing promising paradigm to solve the bi-level optimization problem for NAS.
Limitation & future work: This work is limited in directly adopting off-the-sheel zero-order solvers. There are potential directions for future work: i) We adopt three existing zero-order solvers in Table [ which also suggests new solvers may also be readily reused to improve ZARTS. In contrast, this feature is not allowed in DARTS as there is little option for the gradient-descent solver. ii) Our experiments focus on classification tasks, while ZARTS can also search network architectures for more complex tasks. We derive three ZARTS variants from DARTS variants to speed up the search process. GZAS and MergeZARTS can also reduce the GPU memory requirements, making it possible to search on more complex search spaces or tasks, e.g., object detection and segmentation. iii) ZARTS supports searching for the targets whose gradients are intractable or hard to obtain, e.g., FLOPPs and latency, since ZARTS discards the differentiability assumption and leverages gradient-free algorithms.
Potential negative social impact: Our automatic approach can save many human efforts which may cause job lost in industry. The technology may also be abused by people who may create evil AI.
Acknowledgement
This work was partly supported by National Key Research and Development Program of China A2100A,0 National Natural Science Foundation of China (61972250, 72061127003) and Shanghai Municipal Science and Technology (Major) Project (22511105100, 2021SHZDZX0102),

---

References
[1] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Under- standing and Simplifying One-Shot Architecture Search. In ICML, 2018.
[2] Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 2021.
[3] Kaifeng Bi, Changping Hu, Lingxi Xie, Xin Chen, Longhui Wei, and Qi Tian. Stabilizing darts with amended gradient estimation on architectural parameters, arXiv preprint 1111111910.11831, 2019.
[4] Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware. In ICLR, 2019.
[5] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, AlSec CCS 2017, Dallas, TX, USA, November 3, 2017, 2017.
[6] Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation--assed regularization. In ICML, 2020.
[7] Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation. In ICCV, 2019.
[8] Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. DARTS- robustly stepping out of performance collapse without indicators. In ICLR, 2021.
[9] Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li. Fair darts: Eliminating unfair advantages in differentiable architecture search. ECCV, 2020.
[10] Xuanyi Dong and Yi Yang. Searching for Robust Neural Architecture in Four GPU Hours. In CVPR, 2019.
[11] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
[12] Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gradientless descent: High-dimensional zeroth-order optimization. In ICLR, 2020.
[13] 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. 190.00290..00420,, 2019.
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In CVPR, 2016.
[15) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang. Tobias Weyand, Mareo Andreetto, and Hartwig Adam. Mobilenets: Efficient Convolutional Neural Networks for Mobile Vision Applications. arXiv preprint. arXiv: 10Xx:17004.4861,, 2017.
[16] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In ICML, 2018
[17] Alex Krizhevsky, Geoffrey Hinton, al. Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer, 2009.
[18] Guohao Li, Guocheng Qian, Itzel Delgadillo, Matthias Müller, Ali Thabet, and Bernard Ghanem. Sgas: Sequential greedy architecture search. In CVPR, 2020.
[19] 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
10

---

[20] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable Architecture Search. In ICLR, 2019.
[21] Sijia Liu, Pin- Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O 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, 2020.
[22] Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy, Djallel Bouneffouf, Gregory Bramble, Horst Samulowitz, Dakuo Wang, Andrew Conn, and Alexander Gray. An ADMM based framework for automl pipeline configuration. In AAAI, 2020.
[23] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 2017.
[24] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPSW, 2011.
[25] Hicu Pham, Melody Y Guan, Barret Zoph. Quoc V Le, and Jeff Dean. Efficient Neural Architecture Search via Parameter Sharing. In ICML,, 2018.
[26] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
[27] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1449..0 1556, 2014.
[28] Xingyou Song, Wenbo Gao, Yuxiang Yang, Krzysztof Choromanski, Aldo Pacchiano, and Yunhao Tang. ES-MAML: simple hessian- free meta learning. In ICLR, 2020.
[29] Yun-Yun Tsai, Pin-Yo Yu Chen, and Tsung- Yi Ho. Transfer learning without knowing: Repro- gramming black-box machine learning models with scarce data and limited resources. CoRR, 2020.
[30] Xiaoxing Wang, Xiangxiang Chu, Yuda Fan, Zhexi Zhang, Xiaolin Wei, Junchi Yan, and Xiaokang Yang. ROME: robustifying memory-efficiet NAS via topology disentanglement and gradients accumulation. CoRR, 2020.
[31] Xiaoxing Wang. Chao Xue, Junchi Yan, Xiaokang Yang. Yonggang Hu, and Kewei Sun. Mergenas: Merge operations into one for differentiable architecture search. In IJCAI, 2020.
[32] Sean Welleck and Kyunghyun Cho. Mlc-guided parameter search for task loss minimization in neural sequence modeling. arXiv preprint arXiv:2006.031/ 2020.
[33] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: Stochastic Neural Architecture Search. In ICLR, 2019.
[34] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC-DARTS: Partial Channel Connections for Memory-Efficicee Architecture Search. In ICLR, 2020.
[35] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-efficiee architecture search. In ICLR, 2020.
[36] Yibo Yang, Hongyang Li, Shan You, Fei Wang, Chen Qian, and Zhouchen Lin. ISTA-NAS: efficient and consistent neural architecture search by sparse coding. In NeurIPS, 2020.
[37] Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In ICLR, 2020.
[38] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
[39] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakehi, Thomas Brox, and Frank Hutter. Understanding and Robustifying Differentiable Architecture Search. In ICLR, 2020.
11

---

[40] Pan Zhou, Caiming Xiong, Richard Socher, and Steven Chu-Hong Hoi. insory-isspire path-regularized differential network architecture search. In NeurIPS, 2020.
[41] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc Le. Learning Transferable Architectures for Scalable Image Recognition. In CVPR, 2018.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No]. or [N/A]. You are strongly encouraged to include a justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license the code and datasets? [No] proprietary.
The code and the data are
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] see Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] see
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 4.4
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL.? [Yes] The codes are included in the supplementary material.
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes] See Section 2.2 and 2.3 in supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] The standard deviation of repeated runs reported.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] All the experiments conducted on a single NVIDIA 2080Ti.
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL.? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "OoCAViMMr9d", "reviewer": "Reviewer_LjFh", "summary": "This paper proposes a DARTS variant named ZARTS, which replace the first-order and second-order approximations with zero-order approximations. Experiments on various datasets are conducted to show the superiority of ZARTS.", "questions": "1. Does ZARTS has the same memory cost as DARTS? Can ZARTS directly search on ImageNet?\n\n2. Will the zero-order optimization still be accurate when searching on a huge search space?", "limitations": "Discussion of limitations was provided.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The inaccurate gradient estimation in first-order approximation could result in severe performance collapse and instability problems, this should be highlight in the community. This paper proposes a zero-order approximation method, which seems has better architecture optimization according to the paper's visualizations.\n2. According to Table 5, ZARTS applies to various DARTS variants, and can bring consistent improvements to them.\n\nWeaknesses:\n1. The search cost of ZARTS is similar to DARTS (2nd). Many variants adopt first-order approximation instead of the second-order approximation for faster search, though it has inaccurate gradient estimations; while the proposed zero-order approximation has a similar cost as the second-order one, which may be a major limitation of this work.\n2. Figure 1 is not sufficient enough to show the superiority of ZARTS in architecture optimization. I suggest the authors to conduct experiments on NAS benchmarks (e.g., NAS-Bench-201) to show the accuracy curves of architectures during the searching procedure.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J0RqUeAMpG", "reviewer": "Reviewer_PVAt", "summary": "This paper proposes a new neural architecture search method, namely ZARTS, which solves the bi-level optimization through zero-order optimization. It provides interesting analysis on the differentiable assumption in DARTS and show that the assumption can distort the loss landscape and misleads the search target in Fig. 1. Then this work discards the differentiable assumption and turns to zero-order optimization techniques which to my knowledge have not been used in neural architecture search (NAS) literature. This work also shows the connection between ZARTS and DARTS and points out that ZARTS degrades to the first/second-order DARTS when the iteration number M=0 (for first-order DARTS) or M=1 (for second-order DARTS). The well-designed experiments on the search spaces of DARTS and RobustDARTS verify the effectiveness of ZARTS which are implemented in three variants with the tradeoff between efficiency and efficacy. The paper is technically clear and well written.", "questions": "1. This work introduces to apply three zero-order optimization methods to NAS. I wonder what properties for zero-order optimization methods are necessary to apply to NAS task? This question is also pertinent to the novelty of the paper, for better motivating the adoption of three specific zero-order optimization techniques presented in the paper.\n2. Zero-order optimization methods are known more inefficient than gradient descent method. It would be better if the authors could provide more discussion on why ZARTS converges better than DARTS?\n", "limitations": "I think there is no particular limitation of this work.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n++ This paper provides new and interesting analysis on the limitations of differentiable assumption in DARTS, showing that it can distort the loss landscape resulting in the severe instability issue (in Fig. 1a). \n\n++ By showing the drawbacks of differentiable assumption, it is a good idea to adopt zero-order optimization methods to solve the bi-level optimization problem in NAS.\n\n++ The theoretical analysis on the connection between ZARTS and DARTS are worth publishing, specifically: when the iteration number M is set as 0/1, ZARTS degrades to the first/second-order DARTS.\n\n++ Experiments verify the efficacy of ZARTS, showing that zero-order optimization can effectively alleviate the instability issue of DARTS.\n\n++ This paper provides three variants of ZARTS by combining with three variants of DARTS. Experiments indicate that the variants can speed up the search process and further improve the performance, showing the potential of zero-order optimization methods for NAS.\n\nWeaknesses:\n\n-- Zero-order optimization methods are known more inefficient than gradient descent method, so that ZARTS requires 1 GPU-day to search, which is more time-consuming than other DARTS-based methods.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CSQ8Vju7qbE", "reviewer": "Reviewer_eA5X", "summary": "The authors reexamine the bi-level optimization of NAS and reveal that the differentiable assumption in DARTS can mislead the search process. To verify the analysis, they plot loss landscapes of DARTS and show that first-order approximation of network weight will distort the landscape and drift the optimal. To tackle such an issue, the authors propose ZARTS by utilizing zero-order optimization for architecture parameters. Specifically, they adopt three different zero-order optimizers and sufficient empirical evaluation demonstrates that zero-order optimization unanimously outperforms DARTS. Besides, the authors provide extensive convergence experiments to show the stability of ZARTS. In general, ZARTS provides a new insight for NAS task and achieves good performance on multiple search spaces and datasets.", "questions": "Please see the weakness. Besides, I notice that the variants of ZARTS, i.e., mergeZARTS and GZAS, requires fewer GPU memory, so my question is, can ZARTS directly search on ImageNet?", "limitations": "The limitations were discussed. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and the motivation is clear. The authors first reexamine the bi-level optimization of NAS, then analyze the fundamental limitations in DARTS, and lead to the introduction of ZARTS.\n2. Illustration in Fig.1 is convincing, which provides enough evidence on the drawback of differentiable assumption of DARTS and the advantage of ZARTS against DARTS.\n3. Apart from applying three zero-order optimization methods to NAS, the authors also theoretically show that ZARTS can degrade to DARTS under differentiable assumption.\n4. The experimental results are impressive, showing that ZARTS outperforms DARTS and its variants on multiple search spaces and datasets. Besides, the authors conduct sufficient evaluation about the stability of ZARTS.\n\nWeaknesses:\n1. The authors base their zero-order search methods on three existing zero-order optimization algorithms. Of course it is fine with the current excellent analysis and nontrivial technical adaptation to the NAS problem, while it will be more impressive if the authors could propose their own zero-order algorithm tailored to NAS. I know proposing a new zero-order optimizer it self could be a prominent paper, so at least the authors could provide more discussion on this point.\n2. The searching cost of ZARTS seems to be longer than other variants of DARTS (in Table 3) Can the authors provide more detailed discussion on the searching cost?\n\nOverall, the motivation is clear and the evaluation is sufficient. The major concern is the search cost of ZARS, and I hope the authors could provide more analysis in the rebuttal.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept