Year: 2021

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/secondorder 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.

text: 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/secondorder 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.

heading: 1 INTRODUCTION
text: Despite their success, neural networks are still designed mainly by humans (Simonyan & Zisserman, 2014; He et al., 2016; Howard et 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 as bi-level optimization for network architectures and operation weights.
One-shot NAS (Bender et al., 2018) is a popular search framework that regards neural architectures as directed acyclic graphs (DAG) and constructs a supernet with all possible connections and operations in the search space. DARTS (Liu et al., 2019) 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 a first-order approximation to estimate the gradients of architecture parameters, which is biased and may lead to 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 a 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 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 on multiple public benchmarks.
In a nutshell, this paper sheds light on the frontier of NAS in the following aspects:
1) Establishing zero-order based robust paradigm to solve bi-level optimization for NAS. Differentiable 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, as 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 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-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 discover effective architectures on various benchmarks. In particular, the searched architecture achieves 75.7% top-1 accuracy on ImageNet, outperforming DARTS and most of its variants.

heading: 2 RELATED WORK
text: One-shot Neural Architecture Search. Bender et al. (2018) construct a supernet so that all candidate architectures can be seen as its 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 & Hsieh, 2020) point out the instability issue of DARTS, i.e., skip-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 parameters and network weights. DARTS (Liu et al., 2019) proposes first/second-order approximations to estimate gradients of architecture parameters so that they can be trained by gradient descent algorithms. However, we show that such approximation will distort the loss landscape and mislead the training of architecture parameters. Amended-DARTS (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 gradient-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 robustness 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 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 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-based methods.

heading: 3 BI-LEVEL OPTIMIZATION IN DARTS
text: Following one-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 {xi}Ni=1, which represents latent feature maps. Each edge ei,j contains multiple operations {oi,j , o ∈ O}, whose importance is represented by architecture parameters αoi,j . Therefore, NAS can be modeled as a bi-level optimization problem by alternately updating the operation weights ω (parameters within candidate operations on each edge) and the architecture parameters α:
min α Lval(ω∗(α),α); s.t. ω∗(α) = arg min ω Ltrain(ω,α). (1)

heading: 3.1 FUNDAMENTAL LIMITATIONS IN THE DARTS FRAMEWORK
text: By enforcing an unverified (and in fact difficult to verify) assumption that the search loss Lval(ω∗(α),α) is differentiable w.r.t. α, DARTS (Liu et al., 2019) proposes a second-order approximation for the optimal weights ω∗(α) by applying one-step gradient descent:
ω∗(α) ≈ ω∗2nd(α) = ω − ξ∇ωLtrain(ω,α) = ω′, (2)
where ξ is the learning rate to update network weights. Thus the gradient of the loss function w.r.t. α, ∇αLval(ω∗(α),α), can be computed by the chain rule: ∇αLval(ω∗(α),α) ≈ ∇αLval(ω′,α)− ξ∇2α,ωLtrain(ω,α)∇ω′Lval(ω′,α). Nevertheless, the second-order partial derivative is hard to compute, so the authors adopt the difference method, which is proved in Appendix A.1.
To further reduce the computational cost, first-order approximation is introduced by assuming ω∗(α) being independent of α, 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).
ω∗(α) ≈ ω∗1st(α) = w. (3)
The gradient is then simplified as: ∇αLval(ω∗(α),α) ≈ ∇αLval(ω,α), which, however, further exacerbates the estimation bias.
Reexamining the definition of ω∗(α) in Eq. 1, one would note that it is intractable to derive a mathematical expression for ω∗(α), making Lval(ω∗(α),α) even non-differentiable w.r.t. α. Yet DARTS has to compromise with such approximations as Eq. 2 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, which is shown in Fig. 1 and analyzed in the next section.

heading: 3.2 DISTORTED LANDSCAPE AND INCORRECT OPTIMIZATION PROCESS IN DARTS
text: Fig. 1 illustrates the loss landscape with perturbations on architecture parameters α, showing how different approximations of ω∗ affect the search process. We train a supernet for 50 epochs and randomly select two orthonormal vectors as the directions to perturbα. The same group of perturbation directions is used to draw landscapes in Fig. 1(a) and (b) for a fair comparison. Fig. 1(a) shows the loss landscape with the first-order approximation in DARTS, ω∗1st(α) = ω, while Fig. 1(b) shows the loss landscape with more accurate ω∗(α), which is obtained by fine-tuning the network weights ω for 10 iterations for each α. Landscapes (contours) are plotted by evaluating L at grid points ranged from -1 to 1 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 ω∗1st(α) = ω shifts the global minimum and sharpens the landscape 1, which is the representative characteristic of instability issue as pointed out by (Zela et al., 2020b). 2) Accurate estimation for ω∗ leads to a flatter landscape, indicating that the instability issue can be alleviated. Moreover, we display the landscape with second-order approximation ω∗2nd in Appendix A.2, which is also sharp but slightly flatter than
1A “sharp” landscape has denser contours than a “flat” one.
Algorithm 1: ZARTS: Zero-order Optimization Framework for Architecture Search

heading: Hyper-parameters:
text: Operation weights ω, architecture parameters α, sampling number N , iteration number M , update estimation function φ(·).
while not converged do Sample candidates: {ui}Ni=1, and estimate optimal operation weights ω∗(α ± i ) by
descending∇ωLtrain(ω,α±i ) for M iterations, where α ± i = α±ui; Compute descent direction: u∗ = φ ( {ui,ω∗(α±i )}Ni=1 ) ;
Update architecture parameters: α← α+ u∗; ? The sampling strategies and update estimation functions φ(·) for three different zero-order
optimization algorithms are detailed in Table 1.
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 of loss function, while GLD uses direct search. Note that the ZARTS framework is general and can support more configurations besides the listed ones.
Algorithm Sampling strategy Update estimation function φ
(
{ui,ω∗(αi)}Ni=1
)
ZARTS-RS ui ∼ q(u|α), any sphericallysymmetric distribution. u∗ = −ξ · ϕ(d)2µN ∑N i=1 [L(α+ µui)− L(α− µui)]ui
(Eq. 6) ZARTS-MGS ui ∼ q(u|α), any proposaldistribution. u∗ = ∑N i=1 [ c̃(ui|α)∑N j=1 c̃(uj|α) ui ] (Eq. 10) ZARTS-GLD ui ∼ S d−1, a uniform distri-
bution on a unit sphere. u ∗ = arg mini {L(α̂)|α̂ = α, α̂ = α+ ui} (Eq. 12)
Fig. 1 (a). Consequently, we discard the first/second-order approximation in DARTS and instead use more accurate ω∗ coordinated with zero-order optimization.
Figure 1 (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 to an incorrect point.

heading: 4 ZERO-ORDER OPTIMIZATION FOR ARCHITECTURE SEARCH
text: This paper goes beyond the restrictive first/second-order approximation in DARTS and proposes to train architecture parametersα in a zero-order optimization manner, allowing for more accurate estimation forω∗(α). The generic form of our ZARTS framework is outlined in Alg. 1. Specifically, we select three representative methods, including a vanilla zero-order optimization algorithm, random search (RS) (Liu et al., 2020a), and two advanced algorithms: Maximum-likelihood Guided Parameter Search (MGS) (Welleck & Cho, 2020) and GradientLess Descent (GLD) (Golovin et 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(α) , Lval(ω∗(α),α) to denote the objective w.r.t. architecture parameters α ∈ Rd (Eq. 1), and L(α+u) , Lval(ω∗(α+u),α+u), where u is the update for α.

heading: 4.1 ZARTS-RS VIA RANDOM SEARCH
text: Typical zero-order optimization methods have no access to first-order gradient information and construct gradient estimators based on zero-order information, typically, the function evaluation. As discussed in (Liu et 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):
∇̂αL(α) := ϕ(d)
µ L(α+ µu)u, (4)
where u ∼ q is sampled from a spherically symmetric distribution q, µ > 0 is a smoothing parameter, and ϕ(d) is a dimension-dependent factor related to q. Specifically, q can either be a standard multivariate normal distribution N (0, I) with ϕ(d) = 1, or a multivariate uniform distribution on a unit sphere Sd−1 with ϕ(d) = d. Intuitively, ZARTS-RS samples nearby points from α and yields a large updating step if the function value is high, consistent with the definition of the gradient.
Two-point gradient estimator is a natural extension of one-point estimator:
∇̂αL(α) := ϕ(d)
2µ [L(α+ µu)− L(α− µu)]u. (5)
We can also sample and average a batch of gradient estimations as Eq. 6 to reduce the variance of gradient estimators, resulting in the multi-point estimator:
∇̂αL(α) := ϕ(d)
2µN N∑ i=1 [L(α+ µui)− L(α− µui)]ui. (6)
Following the first-order gradient descent algorithms, the architecture parameters α are updated by α ← α − ξ∇̂αL(α) with the learning rate ξ. Our implementation is compatible with all the estimators above, and we use multi-point estimator (Eq. 6) by default.

heading: 4.2 ZARTS-MGS VIA MAXIMUM-LIKELIHOOD GUIDED PARAMETER SEARCH
text: Maximum-likelihood guided parameter search (MGS) is an advanced zero-order optimization algorithm 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(u|α) = p̃(u|α) Z(α) = 1 Z(α) exp
( −L(α+ u)− L(α)
τ
) , (7)
where p̃(u|α) = exp (−[L(α+ u)− L(α)]/τ) is an unnormalized exponential distribution, and Z(α) = ∫ p̃(u|α)du is its normalization coefficient. τ is a temperature parameter controlling the variance of the distribution.
Intuitively, u with higher probability makes a more significant improvement on the objective function. Therefore, the optimal update of architecture parameters can be estimated by u∗ = Eu∼p(u|α)[u]. However, since the probability p(u|α) is an implicit function relying on L(α + u), making it impractical to obtain the expectation, we refer to (Welleck & Cho, 2020) and apply importance sampling to sample from a proposal distribution q(u|α) with known probability function:
u∗ = Eu∼p(u|α)[u] = ∫ p̃(u|α) Z(α) udu = ∫ q(u|α) [ p̃(u|α) Z(α)q(u|α) u ] du
= Eu∼q(u|α) [
p̃(u|α) Z(α)q(u|α) u ] ≈ 1 N N∑ i=1 [ p̃(ui|α) Z(α)q(ui|α) ui ] , û∗, (8)
where {ui}Ni=1 are sampled from the proposal distribution q(u|α). Similarly, the normalization coefficient Z(α) can be computed as follows:
Z(α) = ∫ p̃(u|α)du ≈ 1
N N∑ i=1 [ p̃(ui|α) q(ui|α) ] . (9)
For convenience, we define a ratio representing the weight on each sample as c̃(u|α) = p̃(u|α)q(u|α) . Consequently, the optimal update for architecture parameters in Eq. 8 can be computed by:
û∗ = N∑ i=1 [ c̃(ui|α)∑N j=1 c̃(uj |α) ui ] = N∑ i=1 [ exp (−[L(α+ ui)− L(α)]/τ) /q(ui|α)∑N j=1 exp (−[L(α+ uj)− L(α)]/τ) /q(uj |α) ui ] .
(10) Finally, the architecture parameters are updated by α ← α + û∗. Additional importance sampling diagnostics are conducted to verify the effectiveness of ZARTS-MGS (see results in Appendix A.3).

heading: 4.3 ZARTS-GLD VIA GRADIENTLESS DESCENT
text: Unlike the above two algorithms that estimate gradient or the update for α, Golovin et al. (2020) propose the so-called GradientLess 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. Particularly, 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 is defined as:
Q = max 1≤i≤K
{ |L(α+ ∆i)− L(α)| · ‖α‖
‖∆i‖ · |L(α)|
} . (11)
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 a predefined search radius boundary [r,R], we independently sample candidate updates {ui} for architecture parameters on spheres with various radii {2−kR}log(R/r)k=0 and perform function evaluation at these points. By comparing L(α) and {L(α+ ui)}, α 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 α← α+ u∗.
u∗ = arg min i {L(α̂)|α̂ = α, α̂ = α+ ui} (12)

heading: 4.4 CONNECTION BETWEEN DARTS AND ZARTS
text: The similarity between gradient-estimation-based zero-order optimization and SGD builds an essential 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:
Lµ(α) := Eu∼q′ [L(α+ µu)], (13) where q′ = N (0, I) if q = N (0, I), and q′ = Bd (a multivariate uniform distribution on a unit ball) if q = Sd−1. The unbiasedness of Eq. 4 with respect to∇αLµ(α) is assured by:
Eu∼q [ ∇̂αL(α) ] = ∇αLµ(α), (14)
as proved by (Nesterov & Spokoiny, 2017; Berahas et al., 2021). The two-point and multi-point estimates have a similar unbiasedness condition when Eu∼q[u] = 0, which is satisfied in our case. The bias between ∇̂αL(α) and∇αL(α) is also bounded (Berahas et al., 2021; Liu et al., 2018b):
E [ ‖∇̂αL(α)−∇αL(α)‖22 ] = O(d)‖∇αL(α)‖22 +O ( µ2d3 + µ2d
ϕ(d)
) , (15)
where d, µ, ϕ(d) have the same meanings as those in Sec. 4.1. Consequently, if L(α) is indeed differentiable w.r.t α and the iteration number M is set to 1, ZARTS-RS degenerates to secondorder DARTS with bounded error.
Next, we theoretically show that MGS (Welleck & Cho, 2020) will degenerate to gradient descent algorithm if the first-order Taylor approximation is applied. Then we analyze the relationship between ZARTS-MGS and DARTS. Proposition 1. Assuming that L(α) in Eq. 1 is differentiable w.r.t. α, MGS algorithm (Welleck & Cho, 2020) degenerates to SGD (used in vanilla DARTS) by the first-order Taylor approximation for L(α), i.e., u∗ ∝ −∇αL(α).
Proof. Denote g , ∇αL(α) as the gradient of L. The Taylor series of L at α up to the first order gives L(α+u)−L(α) ≈ u>g. Applying this approximation to the distribution of u (Eq. 7) yields:
p(u|α) = e −u>g/τ
Z(g) , Z(g) = ∫ ‖u‖≤ε e−u >g/τdu. (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∗ =
∫ ‖u‖≤ε u · e −u>g/τdu
Z(g) = − ∇gZ(g) τZ(α,g) = −1 τ ∇g lnZ(g). (17)
Note that u>g = −‖u‖‖g‖cosη, where η is the angle between u and g. According to the symmetry of integral, Z(g) is determined once ‖g‖ is given. Therefore, we can formulate Z(g) as a function of ‖g‖: Z(g) = Z(‖g‖). According to the chain rule:
u∗ = −1 τ ∇g lnZ(g) = − 1 τ ∇g lnZ(‖g‖) = − ∇‖g‖Z(‖g‖) τZ(‖g‖) ∇g‖g‖ = − ∇‖g‖Z(‖g‖) τZ(‖g‖)‖g‖ g. (18)
Since Z(‖g‖),∇‖g‖Z(‖g‖), ‖g‖ are all scalars, we have
u∗ ∝ −g = −∇αL(α) = −∇αLval(ω∗(α),α). (19) That is, the optimal update u∗ in MGS algorithm shares a common direction with the negative gradient −∇αL(α), as used by gradient descent. 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 ω∗ is estimated by ω∗1st and ω ∗ 2nd, respectively. In general, ZARTS-RS/-MGS can degenerate to DARTS, given the differentiability assumption.
However, unlike DARTS, which has to estimateω∗(α) byω∗1st orω ∗ 2nd to satisfy the differentiablity property of Lval and update α by gradient descent algorithm, ZARTS, without such assumptions, can compute ω∗(α) 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.

heading: 5 EXPERIMENTS
text: In this section, we first verify the stability of our ZARTS (with its three variants RS, MGS, GLD) on the four popular search spaces of R-DARTS (Zela et al., 2020b) on three datasets including CIFAR10 (Krizhevsky et al., 2009), CIFAR-100 (Krizhevsky et al., 2009), and SVHN (Netzer et al., 2011). Note that though ZARTS-GLD performs best in Table 2, and 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-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 our 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) to 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.

heading: 5.1 STABILITY EVALUATION
text: The instability issue of gradientbased NAS methods has recently drawn increasing attention. Amended-DARTS (Bi et al., 2019) shows that after searching by DARTS for 200 epochs, skip-connection gradually dominates the discovered architectures. R-DARTS (Zela et al., 2020b) proposes four search spaces, S1-S4, which amplify the instability of DARTS, as such dominance occurs after only 50 epochs of searching. These studies expose the instability of gradient-based methods. To verify the stability of our method, we search on S1-S4 proposed by R-DARTS and conduct convergence analysis following Amended-DARTS.
Performance on S1-S4. We first search on the four spaces on CIFAR-10, CIFAR-100, and SVHN. Our evaluation settings are the same as R-DARTS (Zela et al., 2020b). Specifically, for CIFAR-10,
the discovered models on S1 and S3 are constructed by 20 cells with 36 initial channels; models on S2 and S4 have 20 cells with 16 initial channels. For CIFAR-100 and SVHN, all the models on S1-S4 have 8 cells and 16 initial channels. Four parallel tests are conducted on each benchmark, among which the best is reported in 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 as R-DARTS, which verifies our analysis in Fig. 1, i.e., the coarse estimation ω∗1st in DARTS distorts the landscape and causes instability. Additionally, to compare with SDARTS (Chen & Hsieh, 2020), we follow its experiment settings by increasing the number of cells and initial channels to 20 and 36 with results reported in Appendix B.4.
Convergence Analysis. The convergence ability of NAS methods describes whether a 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-DARTS (Bi et al., 2019) empirically shows that DARTS has a poor convergence ability: accuracy of the supernet increases but the ultimate performance of the searched network drops. Following Amended-DARTS, we run ZARTS and DARTS for 200 epochs and show the trend of performance and number of parameters in Fig. 2. 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 perform 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 significantly 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 our method.

heading: 5.2 COMPARISON WITH PEER METHODS ON THE SEARCH SPACE OF DARTS
text: To show the efficacy and effectiveness of our method, we search and evaluate on DARTS’s search space on both CIFAR-10 and CIFAR-100. Additionally, the models searched on CIFAR-10 are transferred to ImageNet to evaluate the transferability of our method. The search space and settings follow DARTS (Liu et al., 2019), as is 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.54% best accuracy on CIFAR-10, outperforming DARTS and its variants. Also, compared with Amended-DARTS that approximates optimal operation weights ω∗(α) 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% and 84.54% for mean and best accuracy (i.e. 1- error%), on CIFAR-100, outperforming the compared methods by more than 1%.
Results on ImageNet. For transferability test, we follow the settings of DARTS to 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 a base learning rate of 0.5. We utilize the same data 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 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 Appendix B.6, which has fewer skip connection operations than DARTS.

heading: 6 FURTHER DISCUSSION AND CONCLUSION
text: The proposed ZARTS has opened new possible space for future work at least in the following aspects: 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 to DARTS, which in 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 to reduce the memory cost as well as 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 & Hsieh, 2020). 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 (Bi et al., 2019). To step out of such a bottleneck, this work proposes a robust search framework named ZARTS, allowing for higher-order approximation for ω∗(α) and supporting multiple combinations of zeroorder 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 manages to apply zero-order optimization to one-shot NAS, which provides a promising paradigm to solve the bi-level optimization problem for NAS.

heading: A APPENDIX

heading: A.1 ESTIMATION FOR SECOND-ORDER PARTIAL DERIVATIVE IN DARTS
text: Liu et al. (2019) introduce second-order approximation to estimate optimal network weights, i.e., ω∗ ≈ ω′ = ω − ξ∇ωLtrain(ω,α), so that ∇αLval(ω∗(α),α) ≈ ∇αLval(ω′,α) − ξ∇2α,ωLtrain(ω,α)∇ω′Lval(ω′,α). However, the second-order partial derivative is hard to compute, so the authors estimate it as follows:
∇2α,ωLtrain(ω,α)∇ω′Lval(ω′,α) ≈ ∇αLtrain(ω+,α)−∇αLtrain(ω−,α)
2 , (20)
where ω± = ω ± ∇ω′Lval(ω′,α), and = 0.01‖∇ω′Lval(ω′,α)‖2 . Here, we prove that the above approximation in Eq. 20 is difference method.
Proof. First of all, to simplify the writing, we make the following definitions:
f(ω,α) = ∇αLtrain(ω,α), g(ω,α) = Lval(ω,α). (21)
Then the left term in Eq. 20 can be simplified as:
∇2α,ωLtrain(ω,α)∇ω′Lval(ω′,α) = ∇ωf(ω,α) · ∇ω′g(ω′,α) (22)
= ∇ωf(ω,α) · ∇ω′g(ω′,α) ‖∇ω′g(ω′,α)‖2 · ‖∇ω′g(ω′,α)‖2 = ∇ωf(ω,α) · l · ‖∇ω′g(ω′,α)‖2, (23)
where l = ∇ω′g(ω ′,α)
‖∇ω′g(ω′,α)‖2 is a unit vector. We notice ∇ωf(ω,α) · l is the directional derivative of
f(ω,α) along direction l, which can be estimated by difference method with a small perturbation ′ = 0.01:
∇ωf(ω,α) · l · ‖∇ω′g(ω′,α)‖2 ≈ f(ω + ′l,α)− f(ω − ′l,α)
2 ′ · ‖∇ω′g(ω′,α)‖2 (24)
Moreover, we define = ′ ‖∇ω′g(ω′,α)‖2 . Then ω ± ′l = ω ± ∇ω′g(ω′,α) , ω±, so Eq. 24 can be simplified as:
f(ω + ′l,α)− f(ω − ′l,α) 2 ′ · ‖∇ω′g(ω′,α)‖2 = f(ω+,α)− f(ω−,α) 2 . (25)
Substituting f(ω,α) in Eq. 21 with Eq. 25 results in Eq. 20. Therefore second-order approximation in DARTS utilizes difference method, which is also a zero-order optimization algorithm.

heading: A.2 LOSS LANDSCAPE W.R.T. ARCHITECTURE PARAMETERS
text: To draw loss landscapes w.r.t. α, we train a supernet for 50 epochs and randomly select two orthonormal vectors as the directions to perturb α. The same group of perturbation directions is used to draw landscapes for a fair comparison. Landscapes are plotted by evaluating L at grid points ranged from -1 to 1 at an interval of 0.02 in both directions. Fig. 3 illustrates landscapes (contours)
w.r.t. α under different order of approximation for optimal network weights, showing that both firstand second-order approximation sharpen the landscape and in turn lead to incorrect global minimum. In this work, we obtain ω∗(α) by fixing α and fine-tuning network weights for M iterations (Fig. 3 (c)). Selection of M is also analyzed in Appendix B.3, showing that M = 10 iterations is accurate enough to estimate optimal network weights.

heading: A.3 DETAILS OF ZARTS-MGS ALGORITHM
text: Selection of the Proposal Distribution q(u|α). Since the probability function of distribution p is intractable, we sample from a proposal distribution q and approximate the optimal update of architecture parameters by Eq. 10. The proposal distribution q affects the efficiency of sampling. Specifically, an ideal q 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 a mixture of two Gaussian distributions, one of which is centered at the negative gradient of the loss function with current weights:
q(u|α) = (1− λ)N (−∇αLval(ω,α), σ2) + λN (0, σ2), (26)
where σ is the standard deviation. Intuitively, first-order DARTS (Liu et al., 2019) gives a hint: it updates the architecture parameters α in the direction of −∇αLval(ω,α). 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 is indeed appropriate in our case, we evaluate the effectiveness of q (the proposal distribution) quantitatively by the following experiments. According to Owen (2013), effective sample size (ESS) Ne is a popular indicator defined as Ne = 1∑N
i=1 c 2 i
. For N samples, a
larger Ne ∈ [1, N ] 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 numberN 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 Ne may “saturate”).
As a further exploration, we define effective sample ratio (ESR)Re as the ratio of effective sampling to all samples:
Re = Ne N . (27)
The value of Re denotes the bias between the target distribution p and proposal distribution q, and a smaller value indicates a greater difference. Re is plotted against epochs for various N in Fig. 4(b). On the one hand, Re at epoch 50 stabilizes at 0.7 as N increases, which is an acceptable level of bias between p and q and supports our choice of q; on the other hand, we notice Re 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.

heading: B SUPPLEMENTARY EXPERIMENTS

heading: B.1 DETAILS OF SEARCH SPACES
text: DARTS’s Standard Search Space. The operation set O contains 7 basic operations: skip connection, max pooling, average pooling, 3 × 3 separable convolution, 5 × 5 separable convolution, 3×3 dilated separable convolution, and 5×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, we 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 to ImageNet (Deng et al., 2009). Additionally, in our convergence analysis, we search by DARTS and ZARTS in this search space for 200 epochs.
RDARTS’s Search Spaces S1-S4. To evaluate the stability of search algorithm, RDARTS (Zela et al., 2020a) designs four search spaces where DARTS suffers from instability severely, i.e. 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 setO only contains 3×3 separable convolution and identity for all edges; in S3, O contains 3× 3 separable convolution, identity, and zero for all edges; in S4, O contains 3 × 3 separable convolution and noise operation for all edges. Please refer to Zela et al. (2020a) for more details of the search spaces.

heading: B.2 EXPERIMENT SETTINGS
text: Search Settings. Similar to DARTS, we construct a supernet by stacking 8 cells with 16 initial channels. We apply Alg. 1 to train architecture parameters α 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 hyper-parameters are analyzed in Appendix B.3. The setup for training ω follows DARTS: SGD optimizer with a momentum of 0.9 and a base learning rate of 0.025. Our experiments are conducted on NVIDIA 2080Ti. ZARTS-MGS algorithm is 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.

heading: B.3 ABLATION STUDIES
text: There are two hyper-parameters in our method: sampling number N and iteration number M . As introduced in Section 4, N samples of update step of architecture parameters ui are drawn to estimate the optimal update u∗. For each sampled ui, we approximate the optimal weights ω∗(α+ui) for each sample by training ω for M iterations. To evaluate the sensitivity of our method to the two hyper-parameters above, we conduct ablation studies on the standard search space of DARTS on CIFAR-10 dataset.
Sensitivity to the Sampling Number N . For various sampling numbers N , the average performance of three parallel searches with different random seeds is reported in Table 5. In this experiment, iteration number M is fixed to 10. When N = 2, ZARTS achieves 97.37% accuracy with 2.87M parameters. The number of parameters of searched network increases as N increases, and the performance of searched network gets stable when N ≥ 4. Our method performs 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.31M and 4.26M parameters).
Sensitivity to the Iteration Number M . DARTS and its variants (Xu et al., 2020b; Zela et al., 2020b) assume that the optimal operation weights ω∗(α) is differentiable w.r.t. architecture parameters α, which has not been theoretically proved. In this work, we relax the above assumption and adopt zero-order optimization to updateα. As introduced in Section 4, we perform multiple iterations of gradient descent on operation
weights to accurately estimate ω∗(α). 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 parallel searches with different random seeds in Table 6. In this experiment, we set the sampling number N to 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 ω∗(α) can mislead the search procedure.

heading: B.4 COMPARISION WITH PEER METHODS ON S1-S4
text: Unlike R-DARTS (Zela et al., 2020b) that constructs models by stacking 8 cells and 16 inital channels, 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 on each benchmark by searching with different random seeds. Tabel 7 reports the best and average performance of our method. Note that other methods in Tabel 7 only report the best performance of four parallel tests. According to the results, we observe our ZARTS achieves state-of-the-art on 7 benchmarks and SDARTS-ADV slightly outperforms our ZARTS on 5 benchmarks.

heading: B.5 CONVERGENCE ANALYSIS
text: The convergence ability of NAS methods describes whether a 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 AmendedDARTS (Bi et al., 2019) and evaluates the convergence ability by searching for an extended period (200 epochs). However, since it is time-consuming to train every derived architecture along the search process, we illustrate the trend of number of parameterless operations (pooling and identity operations) in each normal cell to represent the performance of architectures (Fig. 5). Recent works (Chen et al., 2019; Bi et al., 2019; Zela et al., 2020b) show that architecture with more than 4 parameterless operations (especially identity operations) usually has a bad performance, which is a typical phenomenon of the instability issue. Here, we show the number of parameterless operations of our ZARTS in 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, our ZARTS can stably control the number of parameterless 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, as is shown in Fig. 6. The architecture searched on CIFAR-100 dataset is illustrated in Fig. 7. We also conduct experiments in the four difficult search spaces of RDARTS (Zela et al., 2020a) on CIFAR-10 (Krizhevsky et al., 2009), CIFAR-100 (Krizhevsky et al., 2009), and SVHN (Netzer et al., 2011). The searched architectures are illustrated in Fig. 8, Fig. 9, and Fig. 10.

Review summaries:
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.

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.