Title: BETTER OPTIMIZATION FOR NEURAL ARCHITECTURE SEARCH WITH MIXED-LEVEL REFORMULATION

Abstract: Many recently proposed methods for Neural Architecture Search (NAS) can be formulated as bilevel optimization. For efficient implementation, its solution requires approximations of second-order methods. In this paper, we demonstrate that gradient errors caused by such approximation leads to suboptimality, in that such a procedure fails to converge to a (locally) optimal solution. To remedy this problem, this paper proposes MiLeNAS, a mixed-level reformulation for Neural Architecture Search that can be optimized more reliably. It is shown that even when using a simple first-order method on mixed-level formulation, MiLeNAS can achieve lower validation error for NAS problems. Consequently, architectures obtained by our method achieve consistently higher accuracies than those obtained from bilevel optimization. Moreover, the use of first-order updates in our method also leads to faster training. Extensive experiments within convolutional architecture search space validate the effectiveness of our approach.

1. INTRODUCTION:

The success of deep learning in many applications heavily depends on novel neural architectures (He et al., 2016; Huang et al., 2017) . However, most widely-employed architectures are developed manually, making them time-consuming and error-prone. Thus, there has been a growing interest in Neural Architecture Search (NAS), which automates the manual process of architecture design (Bello et al., 2016; Real et al., 2017) . There are three major methods for NAS: evolutionary algorithms (Real et al., 2017; Elsken et al., 2018) , reinforcement learning-based methods (Bello et al., 2016; Pham et al., 2018) , and gradient-based methods (Liu et al., 2018b; Xie et al., 2018; Elsken et al., 2018; Luo et al., 2018) . Evolutionary algorithms and reinforcement learning-based methods require thousands of GPU days to achieve state-of-the-art performance, while gradient-based methods can finish searching within as little as several GPU days.

We can formulate the gradient-based method as a bilevel optimization problem:

EQUATION

EQUATION

where w represents the network weight and α determines the neural architecture. L tr (w, α) and L val (w, α) denote the loss with respect to training data and validation data with w and α, respectively. Though bilevel optimization can accurately describe the NAS problem, it is difficult to solve, as obtaining w * (α) in Equation 2 requires one to completely train a network for each update of α.

Current methods used in NAS to solve bilevel optimization are heuristic, and w * (α) in Equation 2is not satisfied due to first-order or second-order approximation (Liu et al., 2018b; Dong & Yang, 2019) . Hence, these algorithms lack theoretical guarantees and only achieve low convergence rates.

Single-level optimization is another method used to solve the NAS problem and is defined as: min w,α L tr (w, α)

which can be solved efficiently by stochastic gradient descent. However, single-level optimization commonly leads to overfitting with respect to α, meaning that it cannot guarantee that the validation loss L val (w, α) is small. This directly contradicts the objective of NAS, which is to minimize validation loss to find optimal structures. Therefore, single-level optimization is insufficient for NAS.

In this work, we propose mixed-level optimization, which incorporates both bilevel and single-level optimization. Rather than minimizing the validation loss with respect to α with the fully trained weights w * (α) as in Equation 2, or directly minimizing α over the training loss, we minimize both the training loss and validation loss with respect to α, and training loss with respect to w, simultaneously. Note that when the hyperparameter λ (Equation 4) of our mixed-level optimization is set to zero, our mixed-level optimization method degrades to single-level optimization. Alternatively, if λ approaches infinity, our method becomes the bilevel optimization. Since we mix single-level and bilevel optimization, we call our method MiLeNAS, mixed-level optimization based NAS.

MiLeNAS can be a universal method to search for better architectures with a faster convergence rate.

First, it has a computational efficiency similar to that of single-level optimization, but without the concern of overfitting. Second, our method can fully exploit both training data and validation data to update α. Current bilevel optimization-based algorithms, first-order DARTS (Liu et al., 2018b) , SNAS (Xie et al., 2018) , and GDAS (Dong & Yang, 2019) , only use the validation loss in updating α, ignoring the training data. Although second-order DARTS can preserve second-order gradient in both training and evaluation data by approximating w * (α) and using only a single training step, such approximation does not solve the inner optimization (Equation 2) completely. Thus, gradient error caused by such approximation leads to suboptimality. We summarize our contributions as follows:

• We propose a novel solution to the NAS problem, by reformulating it as a mixed-level optimization instead of bilevel optimization, alleviating gradient error caused by approximation in bilevel optimization. This leads to a reliable first order method as efficient as that of the single-level method.

• MiLeNAS can search for better architectures with faster convergence rates. Extensive experiments on image classification demonstrate that MiLeNAS can achieve lower validation error and enjoy a search time three times shorter than bilevel optimization.

• MiLeNAS is a generic framework for gradient-based NAS problems. Our experiments show its versatility in sampling-based methods to obtain better architectures.

The source code of MiLeNAS is available at https://tinyurl.com/milenas-code

2. METHOD:

2.1 MIXED-LEVEL OPTIMIZATION Our mixed-level optimization aims to overcome the difficulty of solving bilevel optimization and to fully exploit information embedded in the training data that is not used by current NAS algorithms when updating architecture parameter α (as shown in Equation 1). We propose mixed-level optimization, which gives a trade-off between single level and bilevel optimization. It maintains a simple implementation and avoids the gradient error problem caused by second-order gradient approximation. Mixed-level optimization additionally overcomes the overfitting problem of singlelevel optimization.

Next, we derive the mixed-level optimization from the single-level optimization, aiming to reduce α overfitting by considering both the training and validation loss. First, the single-level optimization problem is defined as: min

EQUATION

where L tr (w, α) denotes the loss with respect to training data. When training neural network weights w, methods such as dropout are used to avoid overfitting with respect to w. However, directly minimizing Equation 3 to obtain the optimal weight and architecture parameter will lead to overfitting with respect to α. Because α solely depends on the training data, when it is optimized, there is a disparity between L tr (w, α) and L val (w, α). Thus, the objective function defined in Equation 3 is inadequate for neural network search.

To solve the overfitting problem of α, we resort to the most popular regularization method and use L val (w, α) as the regularization term. We minimize Equation 3 subject to the constraint L val (w * (α), α) ≤ L tr (w * (α), α) + δ, where δ is a constant scalar. The above constraint means that the validation loss should not be much larger than the training loss. By the Lagrangian multiplier method, we minimize w * (α) = arg min w L tr (w, α)

min α (1 -λ )L tr (w * (α), α) + λ L val (w * (α), α) -λ δ, with 0 ≤ λ ≤ 1.

Because δ is a constant which does not affect the minimization, after normalizing the parameter before L tr (w(α), α) to one, we obtain the following mixed-level optimization using Equation 3:

EQUATION

where λ is a non-negative regularization parameter that balances the importance of training loss and validation loss. This is different from the bilevel optimization Equation 1 and 2 and single-level optimization Equation 3. Instead of only minimizing the loss with respect to α on the validation data given w as in Equation 1, the minimizer α in Equation 4 must guarantee that both L tr (w, α) and L val (w, α) are small to achieve optimality. As the name mixed-level implies, we mix single-level with bilevel optimization. Specifically, when λ = 0, mixed-level optimization degrades to the single level optimization, while when λ approaches infinity, mixed-level reduces to bilevel optimization. Therefore, it can be stated that both single and bilevel optimization are special cases of mixed-level optimization.

Furthermore, by taking the underlying relation between training loss and validation loss into account, our mixed-level optimization can overcome the overfitting problem and search for architectures with higher accuracy compared to single-level and bilevel optimization.

Algorithm 1 Mixed-Level Optimization based NAS.

1: Input: Set parameter λ (usually set to be one). Initialize w and α. 2: while not converge do 3: Update w = w -ηw∇wLtr(w, α); 4:

Update the structure parameter α using the loss Ltr(w, α) + λL val (w, α).

5: end while:

Our mixed-level optimization can be solved as efficiently as the single-level method. First, we update the network weights w using only training loss. Second, we update α using both training loss and validation loss. Specifically, if we apply the mixed-level method to the gradient-based NAS problem, we only require the first-order method (stochastic gradient descent) to solve equation 4 as follows:

EQUATION

where η w and η α are step sizes related to w and α, respectively. Note that in this simplified first order method, when updating α, we replace w * (α) by its approximation w, and we do not take the derivative with respect to w * (α). As our experiments will demonstrate, this method can optimize the mixed-level objective function more reliably than second order methods for the bi-level formulation, due to the fact that the derivative of w * (α) has significantly less impact in the mixed level formulation than that of the bi-level formulation. It is possible to incorporate second order information, but we find that this is not necessary in practical NAS applications.

2.2. COMPARISON WITH BILEVEL OPTIMIZATION:

Our mixed-level optimization is a generic framework for NAS problems. We apply it to the gradientbased NAS method and compare it with DARTS, whose algorithm is derived from bilevel optimization (Liu et al., 2018b) . When optimizing α, DARTS attempts to approximate the gradient ∇ α L val (w * (α), α) by

EQUATION

where w = w -ξ∇ w L train (w, α) denotes the weights for a one-step forward model. For efficient implementation, DARTS tries to use the finite difference to approximate g 2 in 6 simplified as

∇ α L val (w * (α), α) ≈ ∇ α L val (w , α) -ξ ∇ α L train w + val , α -∇ α L train w - val , α 2 val (7)

where w ± val = w ± val ∇ w L val (w , α). However, DARTS fails to converge to a (locally) optimal solution for two reasons. First, when calculating ∇ α L val (w * (α), α), the optimal w * (α) is not obtained due to one step training. Second, the finite difference approximation of g 2 causes biased gradient error. Thus, the approximation to ∇ α L val used in DARTS leads to a serious drawback: when α is approaching to the optima, the approximate gradient related to α in equation 7 will lead to large deviation from true gradient.

In contrast, our mixed-level method only uses the first-order information (shown in Equation 5), which does not involve gradient errors caused by approximation. Stochastic gradient descent guarantees that our mixed-level optimization converges to a (locally) optimal solution. Furthermore, comparing with Equation 7 and our update of α in Equation 5, we can see that our mixed-level method requires much fewer operations for forward and backward propagation than the bilevel method (2nd-order DARTS), resulting in a faster convergence speed. < l a t e x i t s h a 1 _ b a s e 6 4 = " 5 0 q b i 6 W / a 3 z + s U

2.3. OVERALL PIPELINE:

Z A x W 6 i h b 7 m D U c = " > A A A B 8 X i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 A e 2 o U y 2 m 3 b p Z h N 2 N 0 I J / R d e P C j i 1 X / j z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q K G v S W M S q E 6 B m g k v W N N w I 1 k k U w y g Q r B 2 M b 2 d + + 4 k p z W P 5 Y C Y J 8 y M c S h 5 y i s Z K j 1 k P R T L C a d / r l y t u 1 Z 2 D r B I v J x X I 0 e i X v 3 q D m K Y R k 4 Y K 1 L r r u Y n x M 1 S G U 8 G m p V 6 q W Y J 0 j E P W t V R i x L S f z S + e k j O r D E g Y K 1 v S k L n 6 e y L D S O t J F N j O C M 1 I L 3 s z 8 T + v m 5 r w 2 s + 4 T F L D J F 0 s C l N B T E x m 7 5 M B V 4 w a M b E E q e L 2 V k J H q J A a G 1 L J h u A t v 7 x K W r W q d 1 G t 3 V 9 W 6 j d 5 H E U 4 g V M 4 B w + u o A 5 3 0 I A m U J D w D K / w 5 m j n x X l 3 P h a t B S e f O Y Y / c D 5 / A H + y k M w = < / l a t e x i t >

↵2:

< l a t e x i t s h a 1 _ b a s e 6 4 = " + 9 i p 0 e 2 x O k l x l o q U P r f y 3 j S b c a g 

= " > A A A B 8 X i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 A e 2 o U y 2 m 3 b p Z h N 2 N 0 I J / R d e P C j i 1 X / j z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q K G v S W M S q E 6 B m g k v W N N w I 1 k k U w y g Q r B 2 M b 2 d + + 4 k p z W P 5 Y C Y J 8 y M c S h 5 y i s Z K j 1 k P R T L C a b / W L 1 f c q j s H W S V e T i q Q o 9 E v f / U G M U 0 j J g 0 V q H X X c x P j Z 6 g M p 4 J N S 7 1 U s w T p G I e s a 6 n E i G k / m 1 8 8 J W d W G Z A w V r a k I X P 1 9 0 S G k d a T K L C d E Z q R X v Z m 4 n 9 e N z X h t Z 9 x m a S G S b p Y F K a C m J j M 3 i c D r h g 1 Y m I J U s X t r Y S O U C E 1 N q S S D c F b f n m V t G p V 7 6 J a u 7 + s 1 G / y O I p w A q d w D h 5 c Q R 3 u o A F N o C D h G V 7 h z d H O i / P u f C x a C 0 4 + c w x / 4 H z + A I E 2 k M 0 = < / l a t e x i t > ↵6 < l a t e x i t s h a 1 _ b a s e 6 4 = " s x z c f a c 3 r A b U 2 I 8 d o 3 X z + 8 6 U 8 y E = " > A A A B 8 X i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 9 V j 0 4 r G C / c A 2 l M l 2 0 y 7 d b M L u R i i h / 8 K L B 0 W 8 + m + 8 + W / c t j l o 6 4 O B x 3 s z z M w L E s G 1 c d 1 v Z 2 V 1 b X 1 j s 7 B V 3 N 7 Z 3 d s v H R w 2 d Z w q y h o 0 F r F q B 6 i Z 4 J I 1 D D e C t R P F M A o E a w W j 2 6 n f e m J K 8 1 g + m H H C / A g H k o e c o r H S Y 9 Z F k Q x x 0 r v s l c p u x Z 2 B L B M v J 2 X I U e + V v r r 9 m K Y R k 4 Y K 1 L r j u Y n x M 1 S G U 8 E m x W 6 q W Y J 0 h A P W s V R i x L S f z S 6 e k F O r 9 E k Y K 1 v S k J n 6 e y L D S O t x F N j O C M 1 Q L 3 p T 8 T + v k 5 r w 2 s + 4 T F L D J J 0 v C l N B T E y m 7 5 M + V 4 w a M b Y E q e L 2 V k K H q J A a G 1 L R h u A t v r x M m t W K d 1 6 p 3 l + U a z d 5 H A U 4 h h M 4 A w + u o A Z 3 U I c G U J D w D K / w 5 m j n x X l 3 P u a t K 0 4 + c w R / 4 H z + A I d G k N E = < / l a t e x i t > ↵7 < l a t e x i t s h a 1 _ b a s e 6 4 = " p U K A X r U 2 w q 5 Z F 3 m A g n N 4 U e 8 y l n 0 = " > A A A B 8 X i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 6 r H o x W M F + 4 F t K J P t p l 2 6 2 Y T d j V B C / 4 U X D 4 p 4 9 d 9 4 8 9 + 4 b X P Q 1 g c D j / d m m J k X J I J r 4 7 r f z t r 6 x u b W d m G n u L u 3 f 3 B Y O j p u 6 T h V l D V p L G L V C V A z w S V r G m 4 E 6 y S K Y R Q I 1 g 7 G t z O / / c S U 5 r F 8 M J O E + R E O J Q 8 5 R W O l x 6 y H I h n h t F / r l 8 p u x Z 2 D r B I v J 2 X I 0 e i X v n q D m K Y R k 4 Y K 1 L r r u Y n x M 1 S G U 8 G m x V 6 q W Y J 0 j E P W t V R i x L S f z S + e k n O r D E g Y K 1 v S k L n 6 e y L D S O t J F N j O C M 1 I L 3 s z 8 T + v m 5 r w 2 s + 4 T F L D J F 0 s C l N B T E x m 7 5 M B V 4 w a M b E E q e L 2 V k J H q J A a G 1 L R h u A t v 7 x K W t W K d 1 m p 3 l + V 6 z d 5 H A U 4 h T O 4 A A 9 q U I c 7 a E A T K E h

/ f L U 0 r H Y 1 5 + 9 / q Y S u M z E g 1 Z B I = " > A A A C O X i c b V C 7 S g N B F J 3 1 b X x F L W 0 G g 6 A o Y V c F x U q 0 s b C I Y B I h G 5 a 7 k x s z Z H Z 2 n Z l V w r K / Z e N f 2 A k 2 F o r Y + g N O H o W v A w O H c + 5 j 7 g k T w b V x 3 S d n b H x i c m p 6 Z r Y w N 7 + w u F R c X q n p O F U M q y w W s b o K Q a P g E q u G G 4 F X i U K I Q o H 1 s H v a 9 + u 3 q D S P 5 a X p J d i M 4 F r y N m d g r B Q U K 3 7 E Z Z D 5 I J I O 5 D Q 7 D z K j c r p 5 t 0 O H 2 h b d p r 6 w A 1 t A r X k L 4 o e b W y 9 E k e H N 0 X B E U C y 5 Z X c A + p d 4 I 1 I i I 1 S C 4 q P f i l k a o T R M g N Y N z 0 1 M M w N l O B O Y F / x U Y w K s C 9 f Y s F R C h L q Z D S 7 P 6 Y Z V W r Q d K / u k o Q P 1 e 0 c G k d a 9 K L S V E Z i O / u 3 1 x f + 8 R m r a h 8 2 M y y Q 1 K N l w U T s V 1 M S 0 H y N t c Y X M i J 4 l w B S 3 f 6 W s A w q Y s W E

= " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 Q e 0 o W y 2 k 3 b p Z h N 2 N 0 I J / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q G D Z Z L G L V C a h G w S U 2 D T c C O 4 l C G g U C 2 8 H 4 d u a 3 n 1 B p H s t H M 0 n Q j + h Q 8 p A z a q z 0 o P u 8 X 6 6 4 V X c O s k q 8 n F Q g R 6 N f / u o N Y p Z G K A 0 T V O u u 5 y b G z 6 g y n A m c l n q p x o S y M R 1 i 1 1 J J I 9 R + N j 9 1 S s 6 s M i B h r G x J Q + b q 7 4 m M R l p P o s B 2 R t S M 9 L I 3 E / / z u q k J r / 2 M y y Q 1 K N l i U Z g K Y m I y + 5 s M u E J m x M Q S y

/ + g f H j U 0 n G q K G v S W M S q E 6 B m g k v W N N w I 1 k k U w y g Q r B 2 M b 2 d + + 4 k p z W P 5 Y C Y J 8 y M c S h 5 y i s Z K r R 6 K Z I T 9 c s W t u n O Q V e L l p A I 5 G v 3 y V 2 8 Q 0 z R i 0 l C B W n c 9 N z F + h s p w K t i 0 1 E s 1 S 5 C O c c i 6 l k q M m P a z + b V T c m a V A Q l j Z U s a M l d / T 2 Q Y a T 2 J A t s Z o R n p Z W 8 m / u d 1 U x N e + x m X S W q Y p I t F Y S q I i c n s d T L g i l E j J p Y g V d z e S u g I F V J j A y r Z E L z l l 1 d J q 1 b 1 L q q 1 + 8 t K / S a P o w g n c A r n 4 M E V 1 O E O G t A E C o /

/ + g f H j U 0 n G q K G v S W M S q E 6 B m g k v W N N w I 1 k k U w y g Q r B 2 M b 2 d + + 4 k p z W P 5 Y C Y J 8 y M c S h 5 y i s Z K j 1 k P R T L C a d / r l y t u 1 Z 2 D r B I v J x X I 0 e i X v 3 q D m K Y R k 4 Y K 1 L r r u Y n x M 1 S G U 8 G m p V 6 q W Y J 0 j E P W t V R i x L S f z S + e k j O r D E g Y K 1 v S k L n 6 e y L D S O t J F N j O C M 1 I L 3 s z 8 T + v m 5 r w 2 s + 4 T F L D J F 0 s C l N B T E x m 7 5 M B V 4 w a M b E E q e L 2 V k J H q J A a G 1 L J h u A t v 7 x K W r W q d 1 G t 3 V 9 W

< l a t e x i t s h a 1 _ b a s e 6 4 = " + 9 i p 0 e 2 x O k l x l o q U P r f y 3 j S b c a g = " > A A A B 8 X i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 A e 2 o U y 2 m 3 b p Z h N 2 N 0 I J / R d e P C j i 1 X / j z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q K G v S W M S q E 6 B m g k v W N N w I 1 k k U w y g Q r B 2 M b 2 d + + 4 k p z W P 5 Y C Y J 8 y M c S h 5 y i s Z K j 1 k P R T L C a b / W L 1 f c q j s H W S V e T i q Q o 9 E v f / U G M U 0 j J g 0 V q H X X c x P j Z 6 g M p 4 J N S 7 1 U s w T p G I e s a 6 n

E i G k / m 1 8 8 J W d W G Z A w V r a k I X P 1 9 0 S G k d a T K L C d E Z q R X v Z m 4 n 9 e N z X h t Z 9 x m a S G S b p Y F K a C m J j M 3 i c D r h g 1 Y m I J U s X t r Y S O U C E 1 N q S S D c F b f n m V t G p V 7 6 J a u 7 + s 1 G / y O I p w A q d w D h 5 c Q R 3 u o A F N o C D h G V 7 h z d H O i / P u f C x a C 0 4 + c w x / 4 H z + A I E 2 k M 0 = < / l a t e x i t > ↵6 < l a t e x i t s h a 1 _ b a s e 6 4 = " s x z c f a c 3 r A b U 2 I 8 d o 3 X z + 8 6 U 8 y E = " > A A A B 8 X i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 9 V j 0 4 r G C / c A 2 l M l 2 0 y 7 d b M L u R i i h / 8 K L B 0 W 8 + m + 8 + W / c t j l o 6 4 O B x 3 s z z M w L E s G 1 c d 1 v Z 2 V 1 b X 1 j s 7 B V 3 N 7 Z 3 d s v H R w 2 d Z w q y h o 0 F r F q B 6 i Z 4 J I 1 D D e C t R P F M A o E a w W j 2 6 n f e m J K 8 1 g + m H H C / A g H k o e c o r H S Y 9 Z F k Q x x 0 r v s l c p u x Z 2 B L B M v J 2 X I U e + V v r r 9 m K Y R k 4 Y K 1 L r j u Y n x M 1 S G U 8 E m x W 6 q W Y J 0 h A P W s V R i x L S f z S 6 e k F O r 9 E k Y K 1 v S k J n 6 e y L D S O t x F N j O C M 1 Q L 3 p T 8 T + v k 5 r w 2 s + 4 T F L D J J 0 v C l N B T E y m 7 5 M + V 4 w a M b Y E q e L 2 V k K H q J A a G 1 L R h u A t v r x M m t W K d 1 6 p 3 l + U a z d 5 H A U 4 h h M 4 A w + u o A Z 3 U I c G U J D w D K / w 5 m j n x X l 3 P u a t K 0 4 + c w R / 4 H z + A I d G k N E = < / l a t e x i t >

↵7:

< l a t e x i t s h a 1 _ b a s e 6 4 = " p U K A X r U 2 w q 5 Z F 3 m A g n N 4 U e 8 y l n 0 = " > A A A B 8 X i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 6 r H o x W M F + 4 F t K J P t p l 2 6 2 Y T d j V B C / 4 U X D 4 p 4 9 d 9 4 8 9 + 4 b X P Q 1 g c D j / d m m J k X J I J r 4 7 r f z t r 6 

x u b W d m G n u L u 3 f 3 B Y O j p u 6 T h V l D V p L G L V C V A z w S V r G m 4 E 6 y S K Y R Q I 1 g 7 G t z O / / c S U 5 r F 8 M J O E + R E O J Q 8 5 R W O l x 6 y H I h n h t F / r l 8 p u x Z 2 D r B I v J 2 X I 0 e i X v n q D m K Y R k 4 Y K 1 L r r u Y n x M 1 S G U 8 G m x V 6 q W Y J 0 j E P W t V R i x L S f z S + e k n O r D E g Y K 1 v S k L n 6 e y L D S O t J F N j O C M 1 I L 3 s z 8 T + v m 5 r w 2 s + 4 T F L D J F 0 s C l N B T E x m 7 5 M B V 4 w a M b E E q e L 2 V k J H q J A a G 1 L R h u A t v 7 x K W t W K d 1 m p 3 l + V 6 z d 5 H A U 4 h T O 4 A A 9 q U I c 7 a E A T K E h

/ + g f H j U 0 n G q G D Z Z L G L V C a h G w S U 2 D T c C O 4 l C G g U C 2 8 H 4 d u a 3 n 1 B p H s t H M 0 n Q j + h Q 8 p A z a q z 0 o P u 8 X 6 6 4 V X c O s k q 8 n F Q g R 6 N f / u o N Y p Z G K A 0 T V O u u 5 y b G z 6 g y n A m c l n q p x o S y M R 1 i 1 1 J J I 9 R + N j 9 1 S s 6 s M i B h r G x J Q + b q 7 4 m M R l p P o s B 2 R t S M 9 L I 3 E / / z u q k J r / 2 M y y Q 1 K N l i U Z g K Y m I y + 5 s M u E J m x M Q S y h S 3 t x I 2 o o o y Y 9 M p 2 R C 8 5 Z d X S a t W 9 S 6 q t f v L S v 0 m j 6 M I J 3 A K 5 + D B F d T h D h r Q B A Z D e I Z X e H O E 8 + K 8 O x + L 1 o K T z x z D H z i f P 1 p A j d c = < / l a t e x i t > sj < l a t e x i t s h a 1 _ b a s e 6 4 = " F Z 3 b b k y n L Q l 1 l K h o j f i S P b f F o i k = " > A A A B 6 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 9 F j 0 4 r G i / Y A 2 l M 1 2 0 6 7 d b M L u R C i h P 8 G L B 0 W 8 + o u 8 + W / c t j l o 6 4 O B x 3 s z z M w L E i k M u u 6 3 s 7 K 6 t r 6 x W d g q b u / s 7 u 2 X D g 6 b J k 4 1 4 w 0 W y 1 i 3 A 2 q 4 F I o 3 U K D k 7 U R z G g W S t 4 L R z d R v P X F t R K w e c J x w P 6 I D J U L B K F r p 3 v Q e e 6 W y W 3 F n I M v E y 0 k Z c t R 7 p a 9 u P 2 Z p x B U y S Y 3 p e G 6 C f k Y 1 C i b 5 p N h N D U 8 o G 9 E B 7 1 i q a M S N n 8 1 O n Z B T q / R J G G t b C s l M / T 2 R 0 c i Y c R T Y z o j i 0 C x 6 U / E / r 5 N i e O V n Q i U p c s X m i 8 J U E o z J 9 G / S F 5 o z l G N L K N P C 3 k r Y k G r K 0 K Z T t C F 4 i y 8 v k 2 a 1 4 p 1 X q n c X 5 d p 1 H k c B j u E E z s C D S 6 j B L d S h A Q w G 8 A y v 8 O Z I 5 8 V 5 d z 7 m r S t O P n M E f + B 8 / g B b x I 3 Y < / l a t e x i t >

↵ < l a t e x i t s h a 1 _ b a s e 6 4 = " + w S B P e L 8 n x B d v z P X A 2 q s w h G h f p g = " > A A A B 7 X i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 A e 0 o U y 2 m 3 b t Z h N 2 N 0 I J / Q 9 e P C j i 1 f / j z X / j t s 1 B W x 8 First, since our proposed MiLeNAS is a generic framework, we evaluate our method in two search space settings. The first one is the mixed-operation search space defined in DARTS, where architecture search only performs on convolutional cells to find candidate operations (e.g., convolution, max pooling, skip connection, zero) between nodes inside a cell. To make the search space continuous, we relax the categorical choice of a connection to a softmax over all possible operations:

M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q K G v S W M S q E 6 B m g k v W N N w I 1 k k U w y g Q r B 2 M b 2 d + + 4 k p z W P 5 Y C Y J 8 y M c S h 5 y i s Z K r R 6 K Z I T 9 c s W t u n O Q V e L l p A I 5 G v 3 y V 2 8 Q 0 z R i 0 l C B W n c 9 N z F + h s p w K t i 0 1 E s 1 S 5 C O c c i 6 l k q M m P a z + b V T c m a V A Q l j Z U s a M l d / T 2 Q Y a T 2 J A t s Z o R n p Z W 8 m / u d 1 U x N e + x m X S W q Y p I t F Y S q I i c n s d T L g i l E j J p Y g V d z e S u g I F V J j A y r Z E L z l l 1 d J q 1 b 1 L q q 1 + 8 t K / S a P o w g n c A r n 4 M E V 1 O E O G t A E C o /

EQUATION

The weight p k of the mixed operation ō(i,j) (x) for a pair of nodes (i, j) is parameterized by a vector α i,j . Thus, all architecture operation options inside a network (model) can be parameterized as α. By this definition, MiLeNAS aims at simultaneously optimizing architecture parameters α and model weights w. Another setting is the sampling search space: instead of the mixed operation as Equation 8, GDAS uses differentiable sampler (Gumbel-Softmax) to choose an operation between two nodes in a cell. We substitute bilevel optimization in GDAS with mixed-level optimization to verify the versatility of MiLeNAS. More details of search space are covered in Appendix § A.

Second, we run different optimization methods to compare their validation accuracy, including bilevel optimization, single-level optimization, and MiLeNAS with different λ settings.

Third, the assumption that the model size determines the maximum accuracy motivates us to investigate how optimization methods perform in different model sizes. Throughout the search process, we track the best validation accuracy for every parameter number range, which is calculated by counting the number of convolutional operations in the searched cell. We did not manually define parameter number range because discrete operation choice naturally determines it.

3. EXPERIMENTS AND RESULTS:

In this section, we first introduce our settings and present experimental results on a comparison of MiLeNAS with single-level and bilevel methods. We then demonstrate the applicability of MiLe-NAS in other NAS methods. We further evaluate the accuracy of searched architectures with different model sizes. Finally, we conclude the transferability of MiLeNAS on ImageNet.

3.1. SETTINGS:

MiLeNAS contains two stages: architecture search and architecture evaluation. For the first search and evaluation stages, MiLeNAS is applied to image classification dataset CIFAR-10 ( Krizhevsky et al., 2009) . ImageNet was used for the transferability evaluation. To maintain a fair comparison, a search space definition similar to that of DARTS was chosen. Details regarding search space are continued in Appendix § A. The search was run under two settings: 50 epochs and 200 epochs. Each search round was run four times. In the evaluation stage, the architecture with the highest validation accuracy in the search stage was chosen with confidence (Experimental evidence has proven that the highest validation accuracy for runs in the search stage is consistent with the highest accuracy in the evaluation stage). Our code implementation is based on PyTorch 1.2.0 and Python 3.7.4. Experiments were run on NVIDIA GTX 1080Ti. We correlate our mixed-level method with single-level and bilevel methods by verifying the gap between training accuracy and validation accuracy. For MiLeNAS, we choose three λ settings ( λ = 0.1, λ = 1, λ = 999) to assign different proportions between training loss and validation loss. For single-level method, we update α and w both on the training dataset, while for the bilevel method, we use 2nd-order DARTS (Liu et al., 2018b) . The epoch number was set to 50 (as set in second-order DARTS). In total, the five settings were run four times each, and the final result was based on the averages. From the result shown in Figure 2 , we can see that the single-level method has the largest gap, while the bilevel has the smallest gap.

3.2. CORRELATION WITH SINGLE-LEVEL AND BILEVEL METHODS:

Our mixed-level method lies between them: when λ is small (0.1), the gap is closer to that of the single-level method, while when λ is large (999), the gap is closer to that of the bilevel method. This result confirms our assertion that single-level and bilevel optimizations are special cases of mixed-level optimization with λ = 0 and λ → ∞, respectively.

As demonstrated in Figure 3a , the single-level method gains the lowest validation accuracy due to overfitting, and more importantly, MiLeNAS with λ = 1 and λ = 0.1 achieves higher validation accuracy than the bilevel algorithm (2nd-order DARTS, on a 50-epoch setting). This phenomenon is due to the difficulty in solving a bilevel optimization (MiLeNAS takes only about 1/3 of the computational cost of 2nd-order DARTS). When α is close to optimal, w * in Equation 2 should be solved with high precision and ∇ α L val (w * (α), α) should be well-approximated. However, this cannot be guaranteed in 2nd-order DARTS. Thus, from Figure 3a , we can observe that in the later phase of the search (e.g., after around 35th epoch), 2nd-order DARTS barely increases its validation accuracy. Furthermore, we observe that when λ = 999, MiLeNAS has a high probability of achieving similar validation accuracy to 2nd-order bilevel optimization. This proves our claim that the bilevel optimization is the special case of mixed-level optimization with λ approaching infinity.

To remedy the approximation issue and confirm the effectiveness of MiLeNAS, we performed another experiment running bilevel optimization for the first 35 epochs, then switching to our MiLe-NASmethod. When comparing its result (the green curve in Figure 3a ) to that of the pure bilevel optimization (the blue curve in Figure 3a ), we can see that MiLeNAS continues to improve the validation accuracy in the late phase of the search process. This observation confirms that our mixedlevel algorithm mitigates the gradient approximation issue, and SGD (stochastic gradient descent) guarantees an increased validation accuracy, outperforming bilevel optimization.

Furthermore, as shown in Figure 3b , MiLeNAS is over three times faster than second-order DARTS. MiLeNAS performs a faster search due to its simple first-order algorithm, while the second-order approximation in DARTS requires more gradient computation (discussed in section 2.2). DenseNet-BC (Huang et al., 2017) 3.46 25.6 -manual NASNet-A + cutout (Zoph et al., 2018) 2.65 3.3 2000 RL BlockQNN (Zhong et al., 2018) 3.54 39.8 96 RL AmoebaNet-B + cutout (Real et al., 2019) 2.55 ± 0.05 2.8 3150 evolution Hierarchical evolution (Liu et al., 2017) 3.75 ± 0.12 15.7 300 evolution PNAS (Liu et al., 2018a) 3.41 ± 0.09 3.2 225 SMBO ENAS + cutout (Pham et al., 2018) 2.89 4.6 0.5 RL DARTS (second order) (Liu et al., 2018b) 2.76 ± 0.09 3.3 4 gradient-based SNAS (moderate) (Xie et al., 2018) 2.85 ± 0.02 2.8 1.5 gradient-based SNAS (aggressive) (Xie et al., 2018) 3.10 ± 0.04 2.3 1.5 gradient-based GDAS (Dong & Yang, 2019) 2 In the evaluation stage, 20 searched cells were stacked to form a larger network; it was subsequently trained from scratch for 600 epochs with a batch size of 96 and a learning rate set to 0.03. The CIFAR-10 evaluation results are shown in Table 1 (all architectures were searched using λ = 1). The test error of our method is on par with the state-of-the-art RL-based and evolution-based NAS while using three of magnitude fewer resources. Furthermore, our method outperforms ENAS, 2nd-order DARTS, SNAS, and GDAS with both a lower error rate and fewer parameters. We also demonstrated that our algorithm could search architectures with smaller parameters while maintaining high accuracy. Figure 4 shows examples of searched architectures. Note that recently, several new NAS algorithms have been proposed which achieve lower test errors than MiLeNAS. For example, XNAS achieves a 1.81% test error (Nayman et al., 2019) and SharpDarts achieves 1.93% test error (Hundt et al., 2019) . However, XNAS takes 1500 epochs and well-tuned learning rate to evaluate the chosen architecture as opposed to the 600 epochs used in both in MiLeNAS and DARTS experiments. SharpDarts defines new search spaces, which is the main reason why it obtains such a low test error.

3.3. EVALUATION RESULTS ON CIFAR-10:

We argue that our mixed-level optimization is a generic method that can be applied to these algorithms to improve optimization. For example, we can use the loss function defined in Equation 4instead of Equation 1 to further improve XNAS (Nayman et al., 2019) . Next, we combine mixedlevel optimization with Gumbel-Softmax sampling to improve the performance of GNAS (Dong & Yang, 2019) and further demonstrate the power of mixed-level optimization.

3.3.1. APPLICABILITY TO OTHER NAS METHODS:

MiLeNAS is universal and can substitute the bilevel optimization in other NAS methods to improve their search performance. We performed verification experiments on the Gumbel-Softmax sampling method GDAS (Dong & Yang, 2019) . We reproduced GDAS1 and substituted its bilevel optimization with MiLeNAS, denoted as MiLeNAS (Gumbel). As shown in Figure 5 , MiLeNAS (Gumbel) can achieve a better validation accuracy (GDAS: 65.79%; MiLeNAS (Gumbel): 69.56%), leading to better architectures with lower error rates (GDAS: 2.82%; MiLeNAS (Gumbel): 2.57%). 

ML-NAS (Gumbel):

GDAS

3.3.2. EVALUATION ON DIFFERENT MODEL SIZE:

To further verify the effectiveness of MiLeNAS, we investigated the accuracy of the searched architectures in different model sizes (the parameter number of architecture). In this setting, the epoch number was set to 200 and the parameter range was tracked by using the method introduced in section 2.3. We evaluated the best architecture in each parameter range, and then found the relationship between the parameter number and the model performance (accuracy). From Figure 6 , we learn that our method can also find high-performance architecture with a smaller parameter number. For example, a smaller parameter number of 2.86M gains an error rate of 2.50%, exceeding the reported accuracy reported in DARTS (2.76%, 3.3M). The optimal parameter number range (between 3.5M and 4.5M) is consistent with most reported architectures in other NAS methods. Thus, evaluation on different model size verifies that MiLeNAS can solve the NAS problem better than bilevel method. (Zhang et al., 2018) 26.3 -∼ 5 524 -manual NASNet-A (Zoph et al., 2018) 26.0 8.4 5.3 564 2000 RL AmoebaNet-A (Real et al., 2019) 25.5 8.0 5.1 555 3150 evolution AmoebaNet-C (Real et al., 2019) 24.3 7.6 6.4 570 3150 evolution PNAS (Liu et al., 2018a) 25 Transferability is a crucial criterion used to evaluate the potential of the learned cells (Zoph et al., 2018) . To show if the cells learned through our method on CIFAR-10 can be generalized to larger datasets, we use the same cells as in CIFAR-10 for the classification task on ImageNet. More details of the transfer learning experiments can be found in Appendix B.1.1. Table 2 presents the results of the evaluation on ImageNet and shows that the cell found by our method on CIFAR-10 can be successfully transferred to ImageNet. Our method can find smaller cell architectures that achieve relatively better performance with three times faster than the bi-level method (2nd-order DARTS).

3.4. ARCHITECTURE TRANSFERABILITY EVALUATION ON IMAGENET:



4. RELATED WORKS:

There are three major methods for Neural Architecture Search (NAS). The first method relies on evolutionary algorithms (Real et al., 2017; Elsken et al., 2018) . These algorithms can simultaneously optimize architectures and network weights. However, their demand for enormous computational resources makes them highly restrictive. For example, AmoebaNet requires 3150 GPU days to achieve state-of-the-art performance (Real et al., 2019) . The second method, reinforcement learning (RL) based NAS, formulates the design process of a neural network as a sequence of actions and regards the model accuracy as reward (Bello et al., 2016; Pham et al., 2018) . The third method is gradient-based (Liu et al., 2018b; Xie et al., 2018; Elsken et al., 2018; Luo et al., 2018) . This relaxes the categorical design choices to continuous variables and then leverages the efficient gradient backpropagation so that it can finish searching within as little as several GPU days.

5. CONCLUSION:

We proposed MiLeNAS, a novel perspective to the NAS problem and reformulated it as mixedlevel optimization instead of bilevel optimization. MiLeNAS can alleviate gradient error caused by approximation in bilevel optimization and enjoys the first-order efficiency as that of the singlelevel method. Thus, MiLeNAS can search for better architectures with faster convergence rate. Extensive experiments on image classification have demonstrated that MiLeNAS can gain lower validation error while enjoying a search time three times shorter than 2nd-order bilevel optimization. MiLeNAS is a generic method. Applicability experiments verify that it can be used to the samplingbased method to search for better architectures.

:

As of the publication of this paper, GDAS still has not published the source code.

Figures and Tables:

4 h l d 4 c 7 T z 4 r w 7 H 4 v W N S e f O Y E / c D 5 / A I j K k N I = < / l a t e x i t > t e x i t s h a 1 _ b a s e 6 4 = " 8 I j R 7 z F S 2 L 7 n F Q Q P M 9 u k D t 2 t 6 3 w = " > A A A C F H i c b V B N S 8 N A E N 3 U 7 / o V 9 e h l s Q g V p S R V U D y J X j x 4 U L B W a E q Y b K d 2 6 W Y T d z e W E v I j v P h X v H h Q x K s H b / 4 b 0 9 q D W h 8 M P N 6 b Y W Z e E A u u j e N 8 W o W J y a n p m d m 5 4 v z C 4 t K y v b J 6 p a N E M a y x S E T q O g C N g k u s G W 4 E X s c K I Q w E 1 o P u y c C v 3 6 H S P J K X p h 9 j M 4 Q b y d u c g c k l 3 9 7 2 Q i 7 9 H k 3 P / N S o j J Z 7 O 9 Q D E X d g K 6 O e g A B F i r e H v c z z i r 5 d c i r O E H S c u C N S I i O c + / a H 1 4 p Y E q I 0 T I D W D d e J T T M F Z T g T m B W 9 R G M M r A s 3 2 M i p h B B 1 M x 0 + l d H N X G n R d q T y k o Y O 1 Z 8 T K Y R a 9 8 M g 7 w z B d P R f b y D + 5 z U S 0 z 5 o p l z G i U H J v h e 1 E 0 F N R A c J 0 R Z X y I z o 5 w S Y 4 v m t l H V A A T N 5 j o M Q 3 L 8 v j 5 O r a s X d r V Q v 9 k p H x 6 M 4 Z s k 6 2 S B l 4 p J 9 c k R O y T m p E U b u y S N 5 J i / W g / V k v V p v 3 6 0 F a z S z R n 7 B e v 8 C Z w m d x w = = < / l a t e x i t > min ↵ Ltr(w, ↵) + Lval(w, ↵) < l a t e x i t s h a 1 _ b a s e 6 4 = " b O

X b A j e 7 5 P / k t p u 2 d s r 7 1 7 s l 4 5 P R n H M k D W y T j a J R w 7 I M T k j F V I l j N y T Z / J K 3 p w H 5 8 V 5 d z 6 G p W P O q G e V / I D z + Q U o v a y N < / l a t e x i t > Model Size Accuracy Epoch Accuracy si < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 I M 4 h 6 6 A L e c p Z B G 4 8 P U U B F r 8 0 p g

h S 3 t x I 2 o o o y Y 9 M p 2 R C 8 5 Z d X S a t W 9 S 6 q t f v L S v 0 m j 6 M I J 3 A K 5 + D B F d T h D h r Q B A Z D e I Z X e H O E 8 + K 8 O x + L 1 o K T z x z D H z i f P 1 p A j d c = < / l a t e x i t > sj < l a t e x i t s h a 1 _ b a s e 6 4 = " F Z 3 b b k yn L Q l 1 l K h o j f i S P b f F o i k = " > A A A B 6 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 9 F j 0 4 r G i / Y A 2 l M 1 2 0 6 7 d b M L u R C i h P 8 G L B 0 W 8 + o u 8 + W / c t j l o 6 4 O B x 3 s z z M w L E i k M u u 6 3 s 7 K 6 t r 6 x W d g q b u / s 7 u 2 X D g 6 b J k 4 1 4 w 0 W y 1 i 3 A 2 q 4 F I o 3 U K D k 7 U R z G g W S t 4 L R z d R v P X F t R K w e c J x w P 6 I D J U L B K F r p 3 v Q e e 6 W y W 3 F n I M v E y 0 k Z c t R 7 p a 9 u P 2 Z p x B U y S Y 3 p e G 6 C f k Y 1 C i b 5 p N h N D U 8 o G 9 E B 7 1 i q a M S N n 8 1 O n Z B T q / R J G G t b C s l M / T 2 R 0 c i Y c R T Y z o j i 0 C x 6 U / E / r 5 N i e O V n Q i U p c s X m i 8 J U E o z J 9 G / S F 5 o z l G N L K N P C 3 k r Y k G r K 0 K Z T t C F 4 i y 8 v k 2 a 1 4 p 1 X q n c X 5 d p 1 H k c B j u E E z s C D S 6 j B L d S h A Q w G 8 A y v 8 O Z I 5 8 V 5 d z 7 m r S t O P n M E f + B 8 / g B b x I 3 Y < /l a t e x i t > t e x i t s h a 1 _ b a s e 6 4 = " + w S B P e L 8 n x B d v z P X A 2 q s w h G h f p g = " > A A A B 7 X i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 A e 0 o U y 2 m 3 b t Z h N 2 N 0 I J / Q 9 e P C j i 1 f / j z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b

w D K / w 5 s T O i / P u f C x a C 0 4 + c w x / 4 H z + A I z P j x w = < / l a t e x i t > : architecture parameters ! < l a t e x i t s h a 1 _ b a s e 6 4 = " t l C o s E e 7 a c B 1 5 W G / y 1 y A v F P N x V Y = " > A A A B 7 X i c b V D L S g N B E J y N r x h f U Y 9 e B o P g K e x G Q Y 9 B L x 4 j m A c k S 5 i d 9 C Z j 5 r H M z A p h y T 9 4 8 a C IV / / H m 3 / j J N m D J h Y 0 F F X d d H d F C W f G + v 6 3 V 1 h b 3 9 j c K m 6 X d n b 3 9 g / K h 0 c t o 1 J N o U k V V 7 o T E Q O c S W h a Z j l 0 E g 1 E R B z a 0 f h 2 5 r e f Q B u m 5 I O d J B A K M p Q s Z p R Y J 7 V 6 S s C Q 9 M s V v + r P g V d J k J M K y tH o l 7 9 6 A 0 V T A d J S T o z p B n 5 i w 4 x o y y i H a a m X G k g I H Z M h d B 2 V R I A J s / m 1 U 3 z m l A G O l X Y l L Z 6 r v y c y I o y Z i M h 1 C m J H Z t m b i f 9 5 3 d T G 1 2 H G Z J J a k H S x K E 4 5 t g r P X s c D p o F a P n G E U M 3 c r Z i O i C b U u o B K L o R g + e V V 0 q p V g 4 t q 7 f 6 y U r / J 4 y i i E 3 S K z l G A r l A d 3 a E G a i K K H t E z e k V v n v J e v H f v Y 9 F a 8 P K Z Y / Q H 3 u c P k X + P H w = = < / l a t e x i t > t e x i t s h a 1 _ b a s e 6 4 = " 5 0 q b i 6 W / a 3 z + s U Z A x W 6 i h b 7 m D U c = " > A A A B 8 X i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 A e 2 o U y 2 m 3 b p Z h N 2 N 0 I J / R d e P C j i 1 X / j z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b

6 j d 5 H E U 4 g V M 4 B w + u o A 5 3 0 I A m U J D w D K / w 5 m j n x X l 3 P h a t B S e f O Y Y / c D 5 / A H + y k M w = < / l a t e x i t >

4 h l d 4 c 7 T z 4 r w 7 H 4 v W N S e f O Y E / c D 5 / A I j K k N I = < / l a t e x i t > … si < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 I M 4 h 6 6 A L e c p Z B G 4 8 P U U B F r 8 0 p g = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m q o M e i F 4 8 V 7 Q e 0 o W y 2 k 3 b p Z h N 2 N 0 I J / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b

Figure 1: Overview of the pipeline designed to evaluate MiLeNAS.

Figure 2: Training and Validation Gap (average value with smoothing)

Figure 3: Comparison MiLeNAS with single-level and bilevel methods.

Figure4: Searched Architectures. The left two sub-figures show an architecture that has an error rate of 2.34% with a parameter size of 3.87M; The right two sub-figures show an architecture that has an error rate of 2.50% with a parameter size of 2.86M.

Figure 5: Applying MiLeNAS to GDAS

Comparison with state-of-the-art image classifiers on CIFAR-10

Table content: <table><tr><td>Architecture</td><td>Test Error (%)</td><td>Params Search Cost (M) (GPU days)</td><td>Search Method</td></tr></table>

Comparison with state-of-the-art image classifiers on ImageNet

Table content: <table><tr><td>Architecture</td><td colspan="5">Test Error (%) Params +× Search Cost</td><td>Search</td></tr><tr><td/><td>top-1</td><td>top-5</td><td>(M)</td><td>(M)</td><td>(GPU days)</td><td>Method</td></tr><tr><td colspan="2">Inception-v1 (Szegedy et al., 2015) 30.2</td><td>10.1</td><td>6.6</td><td>1448</td><td>-</td><td>manual</td></tr><tr><td>MobileNet (Howard et al., 2017)</td><td>29.4</td><td>10.5</td><td>4.2</td><td>569</td><td>-</td><td>manual</td></tr><tr><td>ShuffleNet</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposes a new objective for one-shot neural architecture search (NAS) using gradient-based methods. The authors hypothesize that the finite differences approximation in the second-order approximation in DARTS [1] directs the gradients towards bad local minimas in the architecture space. To this end, the authors reformulate the architecture update rule in DARTS as a sum of the one-shot model training loss and the one-shot model validation loss (scaled by some factor lambda). The algorithm is evaluated on the same standard image classification benchmark used in DARTS[1]. I vote for rejecting this submission, mainly for the following reasons: (1) The fixes they propose to previous gradient-based NAS algorithms such as DARTS, SNAS [2], etc., are not clearly motivated and justified, both in theory and practice. (2) Almost no novelty. Except the modified loss, I do not see any difference compared to first-order DARTS. (3) Since the authors used different hyperparameter settings compared to DARTS, it is not clear if the better results in the benchmark results come due to these hyperparameters or their proposed fixes. Main arguments What this paper is trying to improve, is solely based on claims made throughout the paper, and there are no empirical or theoretical evidences to support these claims. For instance saying that not solving *exactly* the inner optimization problem the bi--level settings is always worse than the counterpart, is not true for non-convex inner functions. Performing a few gradient steps to approximate the inner problem solution can act as a regularizer (see [3]). The authors also mention quite often the term *overfitting*. It is not clear in which level the overfitting occurs? Is it in the parameter space or in the architecture space (see [4])? Furthermore, in the NAS context (not only in the single-level optimization scenario), a low value of the validation loss that is minimized during the NAS loop, does not necessarily correlate with the true objective: minimizing the validation/test error of discrete architectures. [4] shows that actually the test accuracy of the final architectures does not correlate with the one-shot validation accuracy, and empirically demonstrate that there is an overfitting on the architectural level. Finally, I did not find the empirical results and experimental settings to be entirely clear and convincing. There are some crucial issues, such as: different hyperparameter settings compared to baselines in the final training of found architectures. Therefore, it is not clear where the contribution in better resuls comes from; or just one run of their methods in some settings in Table 1 and in Table 2. Other comments - In Section 1: SNAS [2] updates both w and alpha using all the training data - Throughout the paper: One-shot validation accuracy or derived architecture validation accuracy when retrained from scratch? Which one do you refer with validation accuracy= - Section 3.3: How did you tune the learning rate (0.03 vs 0.025 in DARTS)? - What are the settings you use for your algorithm in Table 1? Suggested Improvements - Empirical results proving the claims made throughout the paper - Experiments showing how the performance of the architectures found by bi-level optimization relates with the solution returned by the inner problem, i.e. the number of gradient steps towards the approximated w^*. - Evaluation of their methods on other image classification benchmarks and other tasks, such as language modelling. [1] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In ICLR, 2019. [2] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In ICLR, 2019 [3] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In ICML, 2018 [4] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, Frank Hutter. Understanding and Robustifying Differentiable Architecture Search. ArXiv, 2019