Geometry-Aware Gradient Algorithms for Neural Architecture Search
Authors: Liam Li
Mikhail Khodak
Nina Balcan
Ameet Talwalkar
Venue: ICLR 2021 Spotlight (2021)
Keywords: neural architecture search
automated machine learning
weight-sharing
optimization

Abstract: Recent state-of-the-art methods for neural architecture search (NAS) exploit gradient-based optimization by relaxing the problem into continuous optimization over architectures and shared-weights, a noisy process that remains poorly understood. We argue for the study of single-level empirical risk minimization to understand NAS with weight-sharing, reducing the design of NAS methods to devising optimizers and regularizers that can quickly obtain high-quality solutions to this problem. Invoking the theory of mirror descent, we present a geometry-aware framework that exploits the underlying structure of this optimization to return sparse architectural parameters, leading to simple yet novel algorithms that enjoy fast convergence guarantees and achieve state-of-the-art accuracy on the latest NAS benchmarks in computer vision. Notably, we exceed the best published results for both CIFAR and ImageNet on both the DARTS search space and NAS-Bench-201; on the latter we achieve near-oracle-optimal performance on CIFAR-10 and CIFAR-100. Together, our theory and experiments demonstrate a principled way to co-design optimizers and continuous relaxations of discrete NAS search spaces.

Published as a conference paper at ICLR 2021
GEOMETRY-AWARD GRADIENT ALGOIIHTM FOR NEURAL ARCHITECTURE SEARCH
Liam Li Mikhail Khodak*? Maria-Florina Balcan', and Ameet Talwakkr's
1 Determined AI, Carnegie Mellon University, denotes equal contribution me@ 1 liamcci..... com, khodak cmu. edd,, minamffcs. cmu, edu, tawwalkazw@ea edu
ABSTRACT
Recent offte-of methods for neural architecture search (NAS) exploit gradient-basee optimization by relaxing the problem into continuous optimiza- tion over architectures and hhared-weights, understood. We argue for the study of single-level empirical risk minimization to understand NAS with weight-sharing, reducing the design of NAS methods to de- vising optimizers and regularizers that can quickly obtain high-quality solutions to this problem. Invoking the theory of mirror descent, we present geometry- framework that exploits the underlying structure of this optimization to return sparse architectural parameters, leading to simple yet novel algorithms that enjoy fast convergence guarantees and achieve state-of-the-art accuracy on the latest NAS benchmarks in computer vision. Notably, we exceed the best published results for both CIFAR and ImageNet on both the DARTS search space and NAS-Bench- 201; on the latter we achieve near-oracle-optimal performance on CIFAR-10 and CIFAR-100. Together, our theory and experiments demonstrate a principled way to co-design optimizers and continuous relaxations of discrete NAS search spaces.
noisy process that remains poorly
INTRODUCTION
Neural architecture search has become an important tool for automating machine learning (ML) but can require hundreds of thousands of GPU-hours to train. Recently, weight-sharing approaches have achieved state-of-the-art performance while drastically reducing the computational cost of NAS to just that of training a single weights network (Pham al., 2018; Liu et al.. 2019). Methods such as DARTS (Liu et al., 2019), GDAS (Dong & Yang. 2019), and many others (Pham et al., 2018; Zheng et al., 2019; Yang et al., 2020; Xie et al., 2019; Liu al., 2018; Laube & Zell, 2019; Cai et al., 2019; Akimoto et al., 2019; Xu et al., 2020) combine weight-sharing with continuous relaxation of the discrete search space to allow cheap gradient updates, enabling the use of popular optimizers. However, despite some empirical success, weight-sharing remains poorly understood and has received criticism due to (1) rank-disorder (Yu et al., 2020; Zela et al., 2020b; Zhang et al., 2020; Pourchot et al., 2020), where the shared-weights weights performance is poor surrogate of standalone performance, and (2) poor results on recent benchmarks (Dong & Yang. 2020; Zela et al., 2020a).
Motivated by the challenge of developing simple and efficient methods that achieve ofte-oofthheart performance, we study how to best handle the goals and optimization objectives of NAS. We start by observing that weight-sharing subsumes architecture hyperparameters as another set of learned parameters of the shared-weights network, in effect extending the class of functions being learned. This suggests that reasonable approach towards obtaining high-quality NAS solutions is study how to regularize and optimize the empirical risk over this extended class. While many regularization approaches have been implicitly proposed in recent NAS efforts, we focus instead on the question of optimizing architecture parameters, which may not be amenable to standard procedures such as SGD that work well for standard neural network weights. In particular, better-satisfy desirable properties such as generalization and sparsity of architectural decisions, we propose to constrain architecture parameters to the simplex and update them using exponentiated gradient, which has favorable convergence properties due to the underlying problem structure. Theoretically, we draw upon the mirror descent meta- algorithm (Nemirovski Yudin, 1983; Beck & Teboulle, 2003) to give convergence guarantees when using any of broad class of such geometry- to optimize the weight-sharing objective; empirically, we show that our solution leads to strong improvements several NAS benchmarks. We summarize these contributions below:
gradient methods

---

Published as a conference paper at ICLR 2021
1. We argue for studying NAS with weight-sharing a single-level objective over structured function class in which architectural decisions are treated as learned parameters rather than hyper- parameters. Our setup clarifies recent concerns about rank disorder and makes clear that proper regularization and optimization of this objective is critical to obtaining high-quality solutions.
2. Focusing optimization, we propose to improve existing NAS algorithms by re-parameterizing architecture parameters over the simplex and updating them using exponentiated gradient, a variant of mirror descent that converges quickly over this domain and enjoys favorable sparsity properties. This simple modification -hichh which we call the Geometry-Aware Exponentiated Algorithm (GAEA)- is easily applicable to numerous methods, including first-order DARTS Liu et al. (2019), GDAS Dong & Yang (2019), and PC-DARTS (Xu et al., 2020).
3. To show correctness and efficiency of our scheme, we prove polynomial-tine stationary- ppint convergence block-stochastic mirror descent-a family of geometry-awan gradient algorithms that includes GAEA- over continuous relaxation of the single-level NAS objective. To the best of our knowledge these are the first finite-time convergence guarantees for gradient- based NAS.
4. We demonstrate that GAEA improves upon state-of-ther totte methods on three of the latest NAS benchmarks for computer vision. Specifically. we beat the current best results on NAS- MAS-Bench-2201 (Dong & Yang, 2020) by 0. 1.18% on CIFAR-10, 1 1.59% on CIFAR-100, and 0.82% on ImageNet- 16-120, we also outperform the state-of-the-art on the DARTS search space Liu al. (2019), for both CIFAR-10 and ImageNet, and match it on TAS-Bench-1Shon (7ela et al., 2020a).
Related Work. Most optimization analyses of NAS show monotonic improvement (Akimoto et al., 2019), asymptotic guarantees (Yao et al., 2020), or bounds on auxiliary quantities disconnected from any objective (Noy et al., 2019; Nayman et al., 2019; Carlucci et al., 2019). In contrast, we prove polynomial-time stationary-poina convergence on a single-level objective for weight-sharing NAS, so far only studied empirically (Xie et al., 2019; Li et al., 2019). Our results draw upon the mirror descent meta- meta-algorithm (Nemirovski & Yudin, 1983; Beck & Teboulle, 2003) and extend recent nonconvex convergence results Zhang & He (2018) handle alternating descent. While there exist related results (Dang & Lan, 2015) the associated guarantees do not hold for the algorithms we propose. Finally, we note that variant of GAEA that modifies first-order DARTS is related to XNAS (Nayman et al., 2019), whose update also involves exponentiated gradient; however, GAEA simpler and easier to implement.2 Furthermore, the regret guarantees for XNAS do not relate to any meaningful performance measure for NAS such as speed or accuracy, whereas we guarantee convergence on the ERM objective.
2 THE SEIGHT-SHARING OPTIMIZATION PROBLEM
In supervised ML we have a dataset T of labeled pairs (I,, y) drawn from a distribution 'D over input/output spaces X and Y. The goal is use T search function class H for hw : X H> Y parameterized by E Rd that has low expected test loss E(hw (x), y) when using to predict the associated y on unseen samples drawn from D, as measured by some loss E Y Y + [0, oo). A common way to do is by approximate (regularized) empirical risk minimization (ERM), i.c. finding w E IRd with the smallest average loss over T,, via some iterative method Alg, c.g. SGD.
2.1 THE BENEFITS AND CRITICISMS OF WEIGHT-SHARIN FOR NAS
NAS is often viewed as hyperparameter optimization on top of Alg, g, with each architecture a E A corresponding a function class H, (hw,a + Y. w e Rd) be selected by using validation data V c X x Y to evaluate the predictor obtained by fixing a and doing approximate ERM over T:
min eEAA
Σ (lwm..a))))))
S.C.
W. = ATg(T,a)
(a.v))V
Since training individual sets of weights for any sizeable number of architectures is prohibitive, weight-sharing methods instead use single set of shared weights to obtain validation signal about
many architectures at once. In its most simple form, RS-WS (Li & Talwalkar, 2019), these weights
I Code obtain these results has heen made available in the supplementary material *XNAS code does not implement search and, as with previous efforts (Li et al., 2019, OpenReview). we cannot reproduce results after correspondence with the authors. XNAS's best architecture achieves average error of 2. 2.70% under the DARTS evaluation, while GAEA achieves 2.50%. For details see Appendix C.4.
2

---

Published as a conference paper at ICLR 2021
trained to minimize a non-adaptive objective, min E. E ((r.))TT {( (z)) y), where the expectation is over fixed distribution over architectures A. The final architecture is then chosen to maximize the outer (validation) objective in (1) subject to wa = w. More frequently used is a bilevel objective over some continuous relaxation @ of the architecture space A, after which valid architecture is obtained via a discretization step Map
O + A (Pham et al., 2018; Liu et al., 2019);
min BE6
Σ (B.DEV
((bw,o(r)) v) S.t.
W E arg min WER"
Σ ((1m.0(1),))
(2)
(G.N)TT
This objective is not significantly different from (2), since Alg(T, a) approximately minimizes the empirical risk w.r.t. T: the difference is replacing discrete architectures with relaxed architecture parameters 0 E θ, w.r.t. which we can take derivatives of the outer objective. This allows (2) to be approximated via alternating gradient updates w.r.t. w and A. Relaxations can be stochastic, so that Mар(O) is sample from a p-parameterized distribution (Pham et al., 2018; Dong & Yang, 2019). or a mixture, in which case Map(O) selects architectural decisions with the highest weight in a convex combination given by 0 (Liu et al., 2019). We overview this in more detail in Appendix A.
While weight-sharing significantly shortens search (Pham et al., 2018), it draws two main criticisms:
Rank disorder: this describes when the rank of an architecture a according to the validation risk evaluated with fixed shared weights w is poorly correlated with the one using "standalone" weights
Wa = (T, a). This causes suboptimal architectures to be selected after shared weights search (Yu et al., 2020; Zela et al., 2020b; Zhang et al., 2020; Pourchot et al., 2020).
Poor performance: weight-sharing can converge to degenerate architectures (Zela et al., 2020a)
and is outperformed by regular hyperparameter tuning on NAS-Benchh
(Dong & Yang, 2020).
2.2 SINGLE-LEVER NAS AS A BASELINE OBJECT OF STUDY
Why are we able to apply weight-sharing to NAS? The key is that, unlike regular hyperparameters such step-size, architectural hyperparameters directly affect the loss function without requiring dependent change in the model weights w. Thus we can distinguish architectures without retraining simply by changing architectural decisions. Besides enabling weight-sharing, this point reveals that the goal of NAS is perhaps better viewed as regular learning problem over an extended class HA - U.EA H. {/tw.. : X + Y, w Rd a A} that subsumes the architectural decisions as parameters of a larger model class, an unrelaxed "supernet." The natural approach to solving this is by approximate empirical risk minimization, e.g. by approximating continuous objective below on the right using gradient algorithm and passing the output 0 through Map to obtain a valid architecture:
min wERd AEAAA
8(hw,a (2).
min
(()w,0(x))))
(3)
wER OEE
(T.Y)ET
(T.Y)TT
discrete (unrelaxed) supernet (NAS ERM)
continuous relaxation (supernet ERM)
Several works have optimized this single-level objective as an alternative to bilevel (2) (Xie et al., 2019: Li et al., 2019). We argue for its use as the bascline object of study NAS for three reasons:
1. As discussed above, it is the natural first approach to solving the statistical objective of NAS: finding a good predictor Iw E AA in the extended function class over architectures and weights
2. The common alternating gradient approach to the bilevel problem (2) is in practice very similar to alternating block approaches ERM (3); as we will see, there established ways of analyzing such methods for the latter objective, while for the former convergence is known only under very strong assumptions such as uniqueness of the inner minimum (Franceschi et al., 2018).
3. While less frequently used in practice than bilevel, single-level optimization can be very effective: we use it to achieve new state-of-the art results on JAS-Bench-200 (Dong & Yang, 2020).
Understanding NAS as single-level optimization the usual deep learning setting-mall makes weight- sharing natural, not surprising, approach. Furthermore, for methods both single-level and bilevel- that adapt architecture parameters during search, it suggests that we need not worry about rank disorder long as can optimization to find single feasible point that generalizes well; we explicitly do not need a ranking. Non-adaptive methods such as RS-WS still do require rank correlation to select good architectures after search, but they are explicitly not changing 0 and so have no variant solving (3). The single-level formulation thus reduces search method design to well-studied questions of how to best regularize and optimize ERM. While there are many techniques for regularizing weight-sharing ssharing-includingg partial channels (Xu et al.. 2020) and validation Hessian penalization (Zela et al., 2020a) we focus on the second question of optimization.
3

---

Published as a conference paper at ICLR 2021
3 GEOMETRY-AWAR GRADIENT ALGORITHMS
We seek to minimize the (possibly regularized) empirical risk (ww,)) = [+| E E(e,))r ((hw,o(x)) y) over shared-weights
Ie and architecture parameters 0 E O. Assuming we have noisy gradients of w.r.t. w or 0 any point (w, 0) E R x O-i.e. VwJ(w, 0) Vol(w, 0) satisfying WV 0) = V f(w, 0) or EVof(w. w. 0) = Vof(w, respectively- goal is a point where f. or at least its gradient, is small, while taking as few gradients as possible. Our main complication that architecture parameters lie in a constrained, non-Euclidean domain O Most search spaces A are product sets of categorical natural relaxation a product |E] |O] (iimpleee However, NAS methods often re-parameterize O to be unconstrained using a softmax and then SGD or Adam (Kingma & Ba, 2015). Is there better puraamttrizatioo-algrriii
ceasiions-wiihe operation E O to use at edge E E-so the
co-design? We consider a geometry-aware approach that uses mirror descent design NAS methods with better properties depending the domain; key desirable property is to return sparse architectural parameters to reduce loss from post-search discretization.
3.1 BACKGROUND ON MIRROR DESCENT
Mirror descent has many formulations (Nemirovski Yudin, 1983; Beck Teboulle, 2003; Shalev- Shwartz, 2011); the proximal starts by noting that, in the unconstrained case, an SGD update at point 0 E θ = I* given gradient estimate V with step-size 1) is equivalent to
r(()
arg min
(0))()) +
1-100 012
(4)
uERt
Here the first term aligns the output with the gradient while the second (proximal) term regularizes for closeness to the previous point as measured by the Euclidean distance. While the SGD update has been found to work well for unconstrained migh-diimesional optimization, e.g. dcep nets, this choice of proximal regularization may be sub-optimal over constrained space with sparse solutions. The canonical such setting is optimization over the unit simplex, i.e. when θ = {0 E [0, 1] ||0|| 1}- Replacing the fz-regularizer in Equation 4 by the relative entropy u (log u log 0), i.e. the KL-divergence, yields the exponentiated gradient (EG) update (Ø denotes element-wise product): A o exp(-n>
x arg min f)) u +
u (log u Llogu-logo #)
(5)
uEe Note that the full EG update is obtained by f--normalizing the l.h.s. It is well-known that EG over the k-dimensional simplex requires only Ollog k)/ iterations to achieve function value e-away from optimal (Beck & Teboulle, 2003, Theorem 5.1), compared to the Okk/s²) guarantee of gradient descent. This nearly dimension-indepeedeer iteration complexity achieved by choosing regularizer- the KL divergence well-suited to the underlying geometry teenetry-thhee simplex. More generally, mirror descent specified by a distance- gennrratnng function (DGF) Φ that is strongly- convex w.r.t. some norm. á induces Bregman divergence D& (=lullv) = ø (u) - -((v)--( Vo(v)-((- (Bregman, 1967), notion of distance on é that acts as a regularizer the mirror descent update: f))
arg min nee
+
(ull))
(6)
For example, to recover SGD (4) we set (du) |u which is strongly w.r.t. the Euclidean norm, while EG (5) recovered by setting ((u) = u - log u, strongly- w.r.t. the -ormm.
3.2 BLOCK-STOCHAR
MIRROR DESCENT
In the previous section saw how mirror descent can perform better over certain geometries such as the simplex. However, in weight-sharing we are interested in optimizing over a hybrid geometry containing both the shared weights in an unconstrained Euclidean space and the architecture parameters in a non-Euclidean domain. Thus we focus on optimization over two blocks: shared weights w E Ed and architecture parameters 0 E θ the latter associated with a DGF 6 that is strongly-convex w.r.t. some norm ||- ||. In NAS common approach is to perform alternating gradient steps on each domain; for example, both ENAS (Pham et al., 2018) and first-order DARTS (Liu et al., 2019) alternate between SGD on the shared weights and Adam on architecture parameters. This approach is encapsulated in the block-stochastic algorithm described in Algorithm 1, which at each step chooses one block at random to update using mirror descent (recall that SGD is variant) and after T steps returns a random iterate. Algorithm generalizes the single-level variant of both ENAS and first-order DARTS if SGD is used to update 9 instead of Adam, with some mild caveats: in practice blocks are picked cyclically and the algorithm returns the last iterate, not a a random one. To analyze the convergence of Algorithm I we first state some regularity assumptions on the function:
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: Block-stochastie mirror descent optimization of a function f : R + R.
Input: initialization (w(t), ((
RR G. stroglyy-covee DGF @ - R. number of iterations T 1. step-size
for iteration = I...., do sample Unif(w..7
// candomly select update block
if block by = w then
((++1) + w(t) V ((w()))) (00)
// BGD update to shaced weights 11 update to architecture pazams
g(c-1) +- g(t)
else
w ((+l) -- w( g(e-1) +- arg minuce (l) Pa(ullo(t)
// update to shared weights
// update architecture params
Output:
(w("))(()) for n Unif(1......
return randon. iterate
Assumption 1. Suppose & is strongly-convex w.rl. some norm || on convex set O and the objective function f Rd x θ + [0, oc) satisfies the following:
1. --relatieey--weak-coneee gradient bound: E] V fw, 0]1 I G and E| Vof(w I) - G2 for some Gw Gg 2 0.
(w, (w,0) 8) (0( is convex on Rdd θ for some Y > 0.
The second assumption is a standard bound on the gradient norm while the first is generalization of smoothness that allows all smooth and some non-smooth non-convex functions (Zhang & He, 2018).
Our aim will be to show (first-order) ristationary-poiii convergence of Algorithm 1, a standard metric indicating that it has reached a point with no feasible descent direction, up error e; for example, in the unconstrained Euclidean case an e-stationary-pont is simply one where the gradient has squared-norm s The number of steps required to obtain such a point thus measures how fast first-order method terminates. Stationarity is also significant as a necessary condition for optimality.
In θ may be constrained and the gradient may never be small, thus necessitating measure other than gradient norm. We use Bregman stationarity (Zhang & He, 2018, Equation 2. 1), which measures stationary at a point (w, 0) using the Bregman divergence between the point and its proximal map prox, (w, 0) = arg min x Af(u) + Des. (ul) (u//w, /w, 0) for some À > 0:
A (w, Dia.e (w, 0ll prox, (w, 0)) + Dez (prox, (w, 0) ////w////
X
24 and the Bregman divergence Dra.s is that of the DGF 1 ||l 11 + s(0) that encodes the geometry of the joint optimization domain over w E Rd and 0; note that the dependence of the stationarity measure on y is standard (Dang & Lan, 2015; Zhang & He, 2018).
Here X =
To understand why reaching a point (w, 8) with small Bregman stationarity is a reasonable goal, note that the proximal operator prax, has the property that its fixed points, i.c. those satisfying (w, 0) = prox x (w, 0), correspond to points where / has no feasible descent direction. Thus measuring how close (w, O) is to being fixed point of prox--2 is done using the Bregman divergence in (7)-is a good measure of how far away the point is from being stationary point of f. Finally, note that if f is smooth, á is Euclidean, and Ô is unconstrained-iice over architecture parameters as well-then A +. S implies an O(E)-bound on the squared gradient norm, recovering the standard definition of e-stationarity. More intuition on proximal operators can be found in Parikh & Boyd (2013, Section 1.2), while further details on Bregman stationarity and how it relates to other notions of convergence can be found in Zhang & He (2018, Section 2.3).
we are running SGD
27
The following result shows that Algorithm needs polynomially many iterations to finds a point (w, 8) with s-small Bregman stationarity in in-execctaiion
Theorem 1. Let F = [(w((1))0)))))) (((1)) be the value of f at initialization. Under Assumption 1, if AF we run Algorithmm 1 for T 16-F (G + +G)) iterations with step-size n v H(G then EA (w(r), g(r) < e. Here the expectation is over the randomness of the algorithm and gradients.
The proof in the appendix follows from single-block analysis (Zhang & He, 2018, Theorem 3.1) and in fact holds for the general case of any number of blocks associated to any set of strongly-conve DGFs. Although there are prior results for the multi-bles block case (Dang & Lan, 2015), they do not hold for nonsmooth Bregman divergences such the KI. divergence needed for exponentiated gradient.
5

---

Published as a conference paper at ICLR 2021
DARTS Search Space Entropy
WMS-Bench-1Sholt Space Entropy
NAS-Benchh201: CIFAR-10 Entropy
3.5-
3.2-
2,425
6.
Entrayy
2.832
PC-DARTS
GAEA PC DARTS
DIITS tirst order
GAEA DARTS levell
3.975
1.350
6.7
1.323
6.7
Epochs
Figure 1: Sparsity: Evolution over scarch phase epochs of the average entropy of the operation- weights for GAEA and approaches it modifies when run on the DARTS search space (left), NAS- Bench-1Shotl Search Space 1 (middle), and NASBench-201 on CIFAR-10 (right). GAEA reduces entropy much more quickly, allowing it quickly obtain sparse architecture weights. This leads to both faster convergence to a single architecture and a lower loss when pruning at the end of search.
Thus Algorithm 1 returns an e-stationary-pont point given T T= O + GB)/e² iterations, where G bounds the squared f--norm of the shared-weights gradient V. and G3 bounds the squared magnitude of the architecture gradient V o0 as measured by the dual norm || ||. of || ||. Only the last term Go is affected by our choice of DGF Φb The DGF of SGD strongly-convex w.r.t. the fn-norm, which is its own dual, so G is defined via lz. However, for EG the DGF ((u) w.r.t. the l norm,, whose dual is fcc- Since the f2-norm of k-dimensional vector can be Vk times its Ex norm, picking this DGF can lead to better bound on Gg and thus on the number of iterations.
-lg is strongly-convex
3.3 GAEA: A GEOMETRY-AWAR EXPONENTIATED ALGORITIM
Equipped with these single-level guarantees, we turn to designing methods that can in- in-principle be applied to both the single-level and bilevel objectives, seeking parameterizations and algorithms that converge quickly and encourage favorable properties; in particular, we focus on returning architecture parameters that are sparse to reduce loss due to post-search discretization. EG is often considered to converge quickly to sparse solutions over the simplex (Bradley & Bagnell, 2008; Bubeck, 2019), which makes it natural choice for the architecture update. We thus propose GAEA, Geometry- Aware Exponentiated Algorithm in which operation weights on each edge are constrained to the simplex and trained using EG; as in DARTS, the shared weights w are trained using SGD. GAEA can be used as a simple, principled modification to the many NAS methods that treat architecture parameters 0 E θ R [ as real-valued "logits" to be passed through a softmax to obtain mixture weights or probabilities for simplices over the operations O. Such methods include DARTS, PC-DARTS (Xu et al., 2020), and GDAS (Dong & Yang, 2019). To apply GAEA, first re-parameterize to be the product set of [E] simplices, each associated to an edge (i.j) E E; thus 0t.j.o corresponds directly to the weight or probability of operation E O for edge (i.j), not logit. Then, given stochastic gradient (o
((())
and step-size 7) > O, replace the architecture update by EG:
g(++1) + g(() o exp (-nVof(w!) .()))
(multiplicative update)
0(++1)
(8)
0((+1) $30
Y
(simplex projection)
Edeo
(++) ij.
These two simple modifications, re-parameterization and exponentiation, suffice to obtain of the-art results on several NAS benchmarks, as shown in Section 4. Note that to obtain a bilevel algorithm we simply replace the gradient w.r.t. 0 of the training loss with that of the validation loss.
GAEA is equivalent to Algorithm with (0) = E(EJER Eoco 0i.j. log fs. which strongly-
convex w.r.t. || I1 E| over the product of E |0 -simplliess. The dual is ETll Iloo. so if Gw bounds the shared-weights gradient and we have an entry-wise bound on the architecture gradient then GAEA reach e-stationarity in O over SGD, either over the simplex or the logit space. In addition, GAEA encourages sparsity in the architecture weights by using a multiplicative update over simplices and not an additive update over || Obtaining sparse architecture parameters is critical for good performance, both for the mixture relaxation, where it alleviates the effect of discretization on the validation loss, and for the stochastic relaxation, where it reduces noise when sampling architectures.
/ iterations. This can be up to a factor |O] improvement

---

Published as a conference paper at ICLR 2021
Table 1: DARTS: Comparison with SOTA NAS methods on the DARTS search space, plus three results on different search spaces with a similar number of parameters reported at the top for comparison. All evaluations and reported performances of models found on the DARTS search space use similar training routines; this includes auxiliary towers and cutout but no other modifications, e.g. label smoothing (Müller et al., 2019), AutoAugment (Cubuk et al., 2019), Swish (Ramachandran et al., 2017), Squeeze & Excite (Hu et al., 2018), etc. The specific training procedure we use is that of PC-DARTS, which differs slightly from the DARTS routine by a small change to the drop-path probability; PDARTS tunes both this and batch-size. Our results are averaged over 10 random seeds. Search cost is hardware-dependent, we used Tesla V100 GPUs. For more details see Tables 4 & 5.
CIFAR-10 Error Average
Search Cost (GPU Days)
ImageNet Error top-5
Search Cost (GPU Days)
Search Method (source)
Best
top-1
methed
NASNet-A" (Zoph et 2018)
2.65 2.55 + 0.05
2000
26.0
8.4
1800
RL
AmoebaNet-R (Real et al., 2019)
3150
24.3
7.6
3150
evolation
ProxylosNNAS
2019)
2.08
24.9
7.5
8.3
gradient (WS)
ENAS (Pham et al., 2018)
(IS)
RS-W5 (Li & Talwalker, 2019)
2.71
2.85 0.08
0.7
random (WS)
ASNG (Akimoto et 2019)
2019)
2.83 + 0.14
0.1
gradicnt (WS)
SNAS (Xie et al., 2019)
2.85
27.3
9.2
gradient (WS)
DARTS (Ist)' (Liu al., 2019)
3.00 0.14
gradient (WS)
DARTS (2nd) (Liu et al., 2019)
2.76 0.09
26.7
8.7
4.0
gradient (WS)
PDARTS (Chen et al., 2019)
2.50
0.3
24.4
7.4
0.3
gradient (WS)
PC-DARTS! (Xu el al.,, 2020)
2.37 0.07
0.1
24.2
7.3
3.8
gradient (WS)
GAEA PC-DARTS! (ours)
2.50
0.06
7.3
3.8
gradient (WS)
PC-DARTS' (Ku 2020)
(search CIFAR-1O, train on ImageNet) (search CIFAR- 10, train ImageNett
7.8
0.1
gradient (WS)
GAEA PC-DARTS! (ours)
24.3
7.3
0.1
gradient (WS)
Scarch spacc/backbone differ DARTS setting: we show results networks comparable number of parameters. For fair comparison to other work, we show the search cost for training the shared-weights network with single initialization.
4 EMPIRICAL RESULTS USING GAEA
We evaluate GAEA on three different computer vision benchmarks: the large and heavily studied search space from DARTS (Liu et al., 2019) and two smaller oracle evaluation benchmarks, NAS- Bench-1Shotl (Zela et al., 2020a), and differs from the others by applying operations per node instead of per edge, while NAS-Bench-201 differs by not requiring edge-pruning, Since GAEA can modify a variety of methods, e.g. DARTS, PC-DARTS (Xu et al., 2020), and GDAS (Dong & Yang, 2019), on each benchmark we start by evaluating the GAEA variant of the current best method on that benchmark. We show that despite the diversity of search spaces, GAEA improves upon this state-of-the-ar across all three. Note that we use the same step-size for GAEA variants of DARTS/PC-DARTS and do not require weight-decay on architecture parameters. We defer experimental details and hyperparameter settings to the appendix and release all code, hyperparameters, and random seeds for reproducibility.
(Dong & Yang, 2020). NAS-Bench-1Shott
4.1 CONVERGENCE AND SPARSITY OF GAEA
We first examine the impact of GAEA on convergence and sparsity. Figure shows the entropy of the operation weights averaged across nodes for a GAEA-vvriiat and its base method across the three benchmarks, demonstrating that it decreases much faster for GAEA-modified approaches. This validates our expectation that GAEA encourages sparse architecture parameters, which should alleviate the mismatch between the continuously relaxed architecture parameters and the discrete architecture returned. Indeed, we find that post-search discretization on the DARTS search space causes the validation accuracy of the PC-DARTS supernet to drop from 72.17% 15.27%, while for GAEA PC-DARTS the drop is only 75.07% to 33.23%; note that this is shared-weights accuracy, obtained without retraining the final network. The numbers demonstrate that GAEA both (1) achieves better supernet optimization of the weight-sharing objective and (2) suffers less due to discretization.
4.2 GAEA ON THE DARTS SEARCH SPACE
Here we evaluate GAEA on the task of designing CNN cells for CIFAR-10 (Krizhevksy, 2009) and ImageNet (Russakovsky et al., 2015) by using it to modify PC-DARTS (Xu et al., 2020), the current state-of-the-art method. We follow the same three stage process used by both DARTS and RS- SS for search and evaluation. Table displays results on both datasets and demonstrates that GAEA's parameterization and optimization scheme improves upon PC-DARTS. In fact, GAEA PC-DARTS
7

---

Published as a conference paper at ICLR 2021
MMS-Bench-1Sholl Search Space
NAS-Bench-1Shel1: Search Space 2
NAS-Bench-1Shol2: Search Space 3
10
16
15
GALA FC -DRTSS
GALA PC-DARTS
GAAA PC-DNATS
PC-DAATS
PC-DARTS
PC-DARTS
Test Regret
Best from at
Zela (2920)
20
42
10
30
10
30
Epochs
Epochs
Epocht
Figure 2: NAS-Bench-IShotte Online comparison of PC-DARTS and GAEA PC-DARTS in terms of the test regret at each epoch of shared-weights training. i.. the difference between the ground truth test error of the proposed architecture and that of the best architecture in the search space. The dark lines indicate the mean of four random trials and the light colored bands + one standard deviation. The dashed line is the final regret of the best weight-sharing method according to Zela et al. (2020b); note that in our reproduction PC-DARTS performed better than their evaluation on spaces and 3.
outperforms all search methods except ProxylessNAS, which uses 1.5 times many parameters on different scarch space. Thus we improve the state-of-the-ar on the DARTS search space. To meet a CIFAR-10, in Appendix C we report "broad reproducibility" (Li &
higher bar for reproducibility Talwalkar, 2019) by repeating our pipeline with new seeds. While GAEA PC-DARTS consistently finds good networks when selecting the best of four independent trials, multiple trials are required due to sensitivity to initialization, as is true for many approaches (Liu et al., 2019; Xu et al., 2020).
On ImageNet, we follow Xu et al. (2020) by using subsamples containing 10% and 2.5% of the training images from ILSVRC-2012 (Russakovsky et al., 2015) as training and validation sets, respectively. We fix architecture parameters for the first 35 epochs, then GAEA PC-DARTS with step-size 0.1. All other hyperparameters match those of Xu et al. (2020). Table I shows the final performance of both the architecture found by GAEA PC-DARTS on CIFAR-IO and the one found directly on ImageNet when trained from scratch for 250 epochs using the same settings as Xu et al. (2020). GAEA PC-DARTS achieves a top-1 1 test error of 24.0%. which is state-of-the-ar performance in the mobile setting when excluding additional training modifications, e.g. those in the caption. Additionally, the architecture found by GAEA PC-DARTS for CIFAR-10 10 and transferred achieves test error of 24.2%, comparable to the 24.2% error of the one found by PC-DARTS directly on ImageNet. Top architectures found by GAEA PC-DARTS are depicted in Figure 3 in the appendix.
4.3 GAEA ON NAS-BENCH- 1
Bee-Beeehhhhhttt (Zela et al., 2020a) is a subset of NAS-Bench-101 (Ying et al., 2019) that allows benchmarking weight-sharing methods on three search spaces over CIFAR-10 that differ in the number of nodes considered and the number of input edges per node. Of the veight-sharing methods benchmarked by Zela et al. (2020a), we found that PC-DARTS achieves the best performance on 2 of 3 search spaces, we again evaluate GAEA PC-DARTS here. Figure 2 shows that GAEA PC-DARTS consistently finds better architectures on average than PC-DARTS and thus exceeds the performance of the best method from Zela et al. (2020a) on 2 of 3 search spaces. We hypothesize that the benefits of GAEA are limited here due to the near-saturation of NAS methods. In particular, existing methods obtain within 1% test error of the top network in each space, while the latters' test errors when evaluated with different initializations are 0.37%, 0.23% and 0.19%. respectively.
4.4 GAEA ON NAS-BENCH-220
NAS-Bench-201 has one search space on three datasets-CIFAR 10. CIFAR- 100, and ImageNet- 66-120-thar includes 4-node architectures with an operation from O = [none, skip connect, Ix1 convolution, 3x3 convolution, 3x3 avg pool) on each edge, yielding 15625 possible networks. Dong & YYng (2020) report results for several algorithms in the transfer NAS setting, where search is conducted on CIFAR-10 10 and the resulting networks are trained on a possibly different target dataset. Table 2 reports subset of these results alongside evaluations of our implementation of several existing and GAEA- modiiied NAS methods in both the transfer and direct setting. Both the results from Dong & Yang (2020) and our reproductions show that GDAS is the best previous weight- method; we evaluate GAEA GDAS and find that it achieves better results on CIFAR- 100 and similar results on the other two datasets.
8

---

Published as a conference paper at ICLR 2021
Table 2: NAS-Bench-201: Results are separated into traditional hyperparameter optimization al- gorithms with search run on CIFAR-10 (top block), weight-sharing methods with search run on CIFAR-I0 (middle block), and weight-sharing methods run directly on the dataset used for training (bottom block). The use of transfer NAS follows the evaluations conducted by Dong & Yang (2020); unless otherwise stated all non-GAEA results are from their paper. The best results the transfer and direct settings on each dataset are bolded.
Search" (scconds)
CIFAR-10 (test)
CIFAR 100 (tes)
ImugeNet- 16-12-16---00000 (test)
Regular
REA
NIA
93.92 0.30
71.84 1 0.99
45.54 +: 1.03
HO, search
93.70
+
44.57
REINFORCE
N/A
93.85 0.37
71.71 = 1.09
45.25 + 1.18
CIFAR-10
BOHB
N/A
93.61 0.52
70.85 = 1.28
41.12 1.49
RSPS
7587
87.06 = 1.09
58.33 + 4.34
31.14 3.88
(hilevel)
35781
54.30
16.32
Weight
SETN
34139
87.64 0.00
59.05 = 0.24
32.52 0.21
sharing.
GDAS
31609
93.61 0.09
70.70 = 0.30
11.71 0.98
search
DARIS' (bilevel)
106831
54.30
15.32
CIFAR-I0
GAEA DARTS (bilevel)
7930'
91.63 2.57
68.39 4.47
41.59 4.20
DARTS' (ERM)
18112
84.39 3.82
54.81 1 7.08
31.82 1: 4.78
GAEA DARTS (FRM)
9061
94.10 1: 0.29
72.60 + 0.89
0.51 45.81
GDAS!
27923
93.52 0.15
67.52 + 0.15
40.91 0.12
Weight
GAEA GDAS
16754
93.55
70.47 = 0.47
40.91 0.12
sharing.
DARTS (bilevel)
106831
54.30 0.00
15.32 1 0.00
28.96 10.22
direct
GAEA DART' (bilevel)
7930'
91.63 2.57
71.87 + 0.5T
45.69 + 0.56
seurch
DARTS' (ERM)
18112
84.39
3.82
51.26 1 6.14
31.35 +: 7.46
GAEA DARTS (ERM)
9061
94.10 + 0.209
73.43 + 0.13
46.36 0.00
ResNet
N/A
93.97
70.86
43.63
Optimal
N/A
94.37
73.51
47.31
Search cnst reported numning the search algorithm on CIFAR-I0
Scarch measured NVIDIA P100 GPUs.
Our reproduction implementation non-GAEA method.
Since we are interested in improving upon not only GAEA GDAS but also upon traditional hyperpa- rameter optimization methods, we also investigate the performance of GAEA applied to first-order DARTS. We evaluate GAEA DARTS with both single-level (ERM) and bilevel optimization; recall that in the latter case optimize architecture parameters weights w.r.t. the training loss, whereas in ERM there is no data split. GAEA DARTS (ERM) achieves state-of-the-art performance all three datasets in both the transfer and direct setting, exceeding the test accuracy of both weight-sharing and traditional hyperparameter tuning by wide margin. GAEA DARTS (bilevel) performs worse but still exceeds all other methods on CIFAR-100 and ImageNet- 16- studying the single-level case understand NAS; notably, the DARTS (ERM) baseline also improves substantially upon the DARTS (bilevel) baseline.
the validation loss and the shared
11661120 120 in the direct search setting. The result thus also confirms the relevance of
5 CONCLUSION
In this paper we take an optimization- view of NAS, arguing that the design of good NAS algorithms is largely a matter of successfully optimizing and regularizing the supernet. In support of this, we develop GAEA, a simple modification of gradient-based NAS that attains state-of- -f-th--rr performance several computer vision benchmarks while enjoying favorable speed and sparsity properties. We believe that obtaining high-performance NAS algorithms for a wide variety of applications will continue require similar co-design of search space parameterizations and optimization methods, and that our geometry-awann framework can help accelerate this process. In particular, most modern NAS algorithms search over products of categorical decision spaces, to which our approach is directly applicable. More generally, as the field moves towards more ambitious search spaces, e.g. full-network topologies or generalizations of operations such as convolution or attention, these developments may result in new architecture domains for which our work can inform the design of appropriate, geometry-aware optimization methods.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
We thank Jeremy Cohen, Jeffrey Li, and Nicholas Roberts for helpful feedback. This work was supported part by DARPA under cooperative agreements FA875017C014] and HR001120200 1202000, NSF grants CCF-1535961 CCF-1910321, IIS- IIS-1705121, LISS-188017, IIS-1901403 and IIS-2046613, a Microsoft Research Faculty Fellowship, a Bloomberg Data Science research grant, an Amazon Research Award, AWS Machine Learning Research Award, a Facebook Faculty Research Award, funding from Booz Allen Hamilton Inc., a Block Center Grant, a Carnegie Bosch Institute Research Award, and Two Sigma Fellowship Award. Any opinions, findings and conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of DARPA, NSF, any other funding agency.
REFERENCES
Youhei Akimoto, Shinichi Shirakawa, Nozomu Noshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
David M. Bradley and J. Andrew Bagnell. Differentiable sparse coding. In Advances in Neural Information Processing Systems, 2008.
Lev M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, 7:200-211 217, 1967.
Sébastien Bubeck. Five miracles of mirror descent, 2019. Lectures on Some Geometric Aspects of Randomized Online Decision Making.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. Proceedings of the 7th International Conference on Learning Representations, 2019.
Fabio Maria Carlucci, Pedro M. Esperança, Marco Singh, Antoine Yang, Victor Gabillon, Xang Xu, Zewei Chen, and Jun Wang. MANAS: Multi-agent neural architecture search. arXiv, 2019.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Conference on Computer Vision, 2019.
Ekin D. Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoe V. Le. AutoAugment: Learning augmentation strategies from data. In Proceedings of the IEEE Conference on Conference on Computer Vision and Pattern Recognition, 2019.
Cong D. Dang and Guanghui Lan. Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM Journal on Optimization, 25:856-881, 2015.
Terrance DeVries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. Xiv, 2017.
Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four GPU hours. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Xuanyi Dong and Yi Yang. AaS-Bench-200 Extending the scope of reproducible neural architecture search. In Proceedings of the Sth International Conference on Learning Representations, 2020.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimilano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. Proceedings of the 35th International Conference Machine Learning, 2018.
10

---

Published as a conference paper at ICLR 2021
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for mobile vision applications. arXiv, 2017.
Jie Hu, Li Shen, and Gang Sun. suueeze-and-excitation networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018.
Andrew Hundt, Varun Jain, and Gregory D. Hager. sharpDARTS: Faster and more accurate differen- tiable architecture search. arXiv, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local
minima? In Proceedings of the 35th International Conference on Machine Learning, 2018.
Alex Krizhevksy. Learning multiple layers of features from tiny images. Technical report, 2009.
Kevin Alexander Laube and Andreas Zell. Prune and replace NAS. In Proceedings of the IEEE International Conference Machine Learning and Applications, 2019.
Guilin Li, Xing Zhang, Zitong Wang. Zhenguo Li, and Tong Zhang. StacNAS: Towards stable and consistent differentiable neural architecture search. arXiv, 2019.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Proceedings of the Conference on Uncertainty Artificial Intelligence, 2019.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. DARTS+: Improved differentiable architecture search with early stopping. arXiv, 2019.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European Conference on Computer Vision, 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. ShuffleNet V2: Practical guidelines for efficient CNN architecture design. In Proceedings of the European Conference on Computer Vision, 2018
Rafael Müller, Simon Kornblith, and Geoffrey E. Hinton. When does label smoothing help? In Advances in Neural Information Processing Systems, 2019.
Niv Nayman, Asaf Noy, Tal Ridnik, Itamar Friedman, Rong Jin, and Lihi Zelnik-Manor. XNAS: Neural architecture search with expert advice. In Advances in Neural Information Processing Systems, 2019.
Arkadi Nemirovski and David Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Asaf Noy, Niv Nayman, Tal Ridnik, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik- Manor. ASAP: Architecture search, anneal and prune. arXiv, 2019.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3): 123-231, 2013.
Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proceedings of the 35th International Conference Machine Learning, 2018.
Alo is Pourchot, Alexis Ducarouge, and Olivier Sigaud. To share or not to share: A comprehensive appraisal of weight-sharing. arXiv, 2020.
11

---

Published as a conference paper at ICLR 2021
Prajit Ramachandran, Barret Zoph, and Quoe V. Le. Searching for activation functions. arXiv, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211 1-22, 2015.
Shai Shalev-Shwartz. Online learning and online convex optimization, Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Sirui Xie, Hehui Zheng, Chumxiao Liu, and Liang Lin. SNAS: Stochastic neural architecture search.
In Proceedings of the 7th International Conference on Learning Representations, 2019.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC-DARTS: Partial channel connections for memory-efficient architecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Yoshihiro Yamada, Masakazu lawmura, and Koichi Kise. ShakeDrop regularization. arXiv, 2018.
Zhaohui Yang, Yunhe Wang, Xinghao Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. CARS: Continuous evolution for efficient neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
Quanming Yao, Ju Xu, Wei-Wei Tu, and Zhangxing Zhu. Efficient neural architecture search via proximal iterations. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS- Bench- 101: Towards reproducible neural architecture search. In Proceedings of the 36th Interna- tional Conference on Machine Learning, 2019.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakehi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. Proceedings of the 8th International Conference Learning Representations, 2020a.
Arber Zela, Julien Siems, and Frank Hutter. NAS-Bect Bench- Benchmarking and dissecting one- shot neural architecture search. In Proceedings of the 8th International Conference on Learning Representations, 2020b.
Siqi Zhang and Niao He. On the convergence rate of nonconvex optimization. arXiv, 2018.
stochastic mirror descent for nonsmooth
Yuge Zhang, Zejun Lin, Junyang Jiang, Quanlu Zhang, Yujing Wang, Hui Xue, Chen Zhang, and Yaming Yang. Deeper insights into weight sharing in neural architecture search. arXiv, 2020.
Xiawu Zheng, Rongrong Ji, Lang Tang, Baochang Zhang, Jianzhuang Liu, and Qi Tian. Multino- mial distribution learning for effective neural architecture search. In Proceedings of the IEEE International Conference on Computer Vision, 2019.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018
12

---

Published as a conference paper at ICLR 2021
A BACKGROUND ON NAS WITH WEIGHT-SHARING
Here we review the NAS setup motivating our work. Weight-sharing methods almost exclusively use micro cell-based search spaces for their tractability and additional structure (Pham al., 2018; Liu et al., 2019). These search spaces can be represented as directed acyclic graphs (DAGs) with set of ordered nodes N and edges E. Each node ( E N is feature representation and each edge (i,j) E is associated with operation the feature of node j passed node and aggregated with other inputs form 20)) with the restriction that given node j can only receive edges from prior nodes input. Hence, the feature node i is (1) Σj<r (()))((2(()))) Search spaces specified by the number of nodes, the number of edges per node, and the set of operations O that can be applied at each edge. Thus for NAS, A C. {0, 1 is the set of all valid architectures for encoded by edge and operation decisions. Treating both the shared weights w Rd and architecture decisions E AA as parameters, weight-sharing methods train a single network subsuming all possible functions within the search space.
Gradient-basse weight-sharing methods apply continuous relaxations to the architecture space A in order to compute gradients in continuous space Methods like DARTS (Liu et al., 2019) and its variants (Chen et al., 2019; Laube & Zell, 2019; Hundt et al.. 2019; Liang et al., 2019; Noy et al., 2019; Nayman et al., 2019) relax the search space by considering mixture of operations per edge. For example, we will consider a relaxation where the architecture space A = {0, } |]1E) [0] is relaxed into = [0, 1] || with the constraint that Eoco Oijjo = 1, i.e. the operation weights on each edge sum to 1. The feature at node i is then z0() = Ejji EeEo (zz))) To get a valid architecture E A from mixture 0, rounding and pruning are typically employed after the search phase.
An alternative, stochastic approach, such as that used by GDAS (Dong & Yang. 2019), instead uses O-parameterized distributions pe over A to sample architectures (Pham al., 2018; Xie et al., 2019; Akimoto et al., 2019; Cai et al., 2019); unbiased gradients w.r.t. E θ can be computed using Monte Carlo sampling. The goal of all these relaxations to approximately optimize (1) over a E A by optimizing (2) over 0 E O instead. However, both the relaxation and the optimizer critically affect the convergence speed and solution quality. We next present principled approach for understanding both mixture and stochastic methods.
use simple gradient-
approaches
13

---

Published as a conference paper at ICLR 2021
B OPTIMIZATION
This section contains proofs and generalizations of the non-convex optimization results in Section Throughout this section, denotes finite-dimensional real vector space with Euclidean inner product -), R4 denotes the set of nonnegative real numbers, and R denotes the set of extended real numbers {+oo].
B.I PRELIMINARIES
:I Definition 1. Consider a closed and convex subset X' V. For any a > and norm : R+ an eeerywheresuuddfffeeeee
function f X + R called a-strongly-convex W.E. || if
V x, X we have
((y) f(x) + (VI(x), x) 2 y x||
Definition 2. Consider a closed and convex subset X' C V. For any 3 > and norm || R. an continuouslyddiffeeeeene function A x, E X we have
X + R is called 3-strongly-smooth w.r.t || - if
s (Vf()) x)
x|2
Definition 3. Let X be closed and convex subset of The Bregman divergence induced by strictly convex, continuously continoousyydifffeentttb distance-generating function (DGF) Φ X'
D*(xlly) = x(x) o(y) - (Vály), Vx,
By definition, the Bregman divergence satisfies the following properties:
1. Do(x|ly) 2 20x,y X and Do(x|ly) = 0 x y.
2. If é is a-stroogly-coover
norm then is Dol-lly) V X. Furthermore, D (xll)) 2 - y x,y E..
3. If à is D-strongly-smooe w.r.t. norm then so DoC-lly) V X. Furthermore, (x < 1 1 Vx, X.
Definition 4. (Zhang & He. 2018, Desinition 2.1) Consider closed and convex subset X V. For any > and Φ X + R an beerywhere-subdiffeeeniie function f X + IR. is called y-reltively-weakyyyconve (--RWC) w.r.l ó if f()) + + convex X.
Definition 5. (Zhang & He, 2018, Definition 2.3) Consider closed and convex subset X V. For any X > 0, function f + R. and DGF 6 X + the Bregman proximal operator of f
, arg min Xf(u) + (ulx(
ueX
Definition 6. (Zhang & He, 2018, Equation 2.1 Consider closed and convex subset X C V. For any X > 0, function f X + R. and DGF & X' + R the Bregman stationarity of f at any point x is
xx Ds(x| prox, (x)) + (proxx (x)]|x)
X2
14

---

Published as a conference paper at ICLR 2021
B.2 RESULTS
Throughout this subsection let V = X V, be a product space of finite-dimensional real vector spaces 1,, each with an associated norm || ||: : V, + R,, and X X; be a product set of 6 subsets X; C Vi, each with associated I-strongly-conver DGF X + R w.r.t || lli. For each E [6] will use || lls. to denote the dual norm of || l|a and for any element x E X will use X; denote its component in block and x-; denote the component across all blocks other than i. Define the functions || || V + R4 and || ||. + R+ for any x E V by ||x|| = Ei= ||x and |xx|? = Ei ||x,Ii,.. respectively, and the function Φ : X + IE for any x E X' by ((x) = E (x)x). Finally, for any n E we will use [n] to denote the set nl....nn..
Setting 1. For some fixed constants M.L, > 0 for each E [6] we have the the following:
1. f X R. is serrwherr--ubddiffeentiee
with minimum f -o and for all X and each i [b) the restriction x-:) is RW-RWC w.r.f. di.
2. For each i E [b] there exists stochastic oracle G. that for input x E X outputs random vector Gx(x, E) s.t. EeGe(x,E) E 0, fx), where 0xf(x) is the subdifferential set of the restriction f(, (x,x,)) at x4. Moreover, Bel[G, 1),, S L.P.
Define 7 max4e(b] "t and T? Σ T2
Claim 1. ||- |I is a norm on V.
Proof. Positivity and homogeneity are trivial. For the triangle inequality, note that for any À E [0, 1] and any x. E X' we have that
||x + -)yy1 =
Ax: + (1 A)yill?
(A|xx (1- 1113
X
Σ x + +1-
Σ l ll
A||x|| + x)lllI
where the first inequality follows by convexity of the norms || ||, V [b] and the fact that the Euclidean norm on IR. is nondecreasing in each argument, while the second inequality follows by convexity of the Euclidean norm on RR. Setting > and multiplying both sides by 2 yields the triangle inequality.
15

---

Published as a conference paper at ICLR 2021
Algorithm 2: Block-stochastic mirror descent over X' X
Rs given associated DGFs
d; ;. H R.
Input: initialization x()) E X, number of steps 7 1, step-size sequence {m))=1
for iteration E [T] do
sample i Unif b]
set x (f+1) = x (8)
get g = (x(x(*,
set x; [t+1) arg nex; (g u) + Do, (ullx()
Output: & = x() w.p. Eist
Claim 2. 311- lle is the convex conjugate of y 1|?
Proof. Consider any u E V. To upper-bound the convex conjugate note that
||
||x: l 2
sup x)
sup
11, x;)
xE
2
XEV
|x
sup xEV
|| ||:l=
2
i=1
uu 11
|
where the first inequality follows by definition of a dual norm and the second by maximizing each
term w.r.t. ||x,||s- For the lower bound, pick x E V s.t. (u, x2) = ||u,|l,, |x and ||x|
l|
[|ull,,, V e [b]. which must exist by the definition of a dual norm. Then
|x|
x 1I
1
b
1 12
xu.x)
2
2
2
2
2
so supexv (u, -/11x/12 2 1 ||2 completing the proof.
16

---

Published as a conference paper at ICLR 2021
Theorem 2. Let & be the output of Algorithm after T iterations with non-increasing step-size sequence [n Then under Setting foror any f > Ty we have that
96 minnex ((u) + (x EA (8) S
41. 25 21=1
7-7
Σ
where the expectation w.r.t. &e and the randomness of the algorithm.
Proof. Define transforms Ü,, E [b] s.t. U = x, and x = En Ux vx E X. Let G be stochastic oracle that for input
X' outputs G(x,i,E) (x, This implies E = 2/ E.= (x,, E) E Ei= U,0,f(x) = 0f(x) and (x, = Ei D2 (x, < E 17 bT?. Then
x(++1) = U, arg min Tt (g, u) + Da, (ullx()) uEx,
U.U?
arg min ne TU, (x)) nex
(E)), u) + Σ Do (u:llx("))
The (G(x, i, Ex), u) (u(ul|x(0)
arg min ueX
b
Thus Algorithm is equivalent to Zhang & He (2018, Algorithm 1) with stochastic oracle G(x, i, E). step-size sequence {1) 1n/bb//1- and no regularizer. Note that is I-strongly-coovve w.r.t. || and R-RC w.r.t. Ø, so in light Claims and our setup satisfies Assumption of Zhang (2018). The result then follows from Theorem 3.1 of the same.
Corollary 1. Under Setting 1 let & be the output of Algorithm 2 with constant step-size
26(00)- V [T], where f(I) f(x(1)). Then we have 7L2T
2b (f() - f*)
EA 27 (8) &
2
T
where the expectation is w.r.t &. and the randomness of the algorithm. Equivalently, can reach point & satisfying EA (8) S in (xb))((())1"))
stochastic oracle calls.
82
27
17

---

Published as a conference paper at ICLR 2021
B.3 A SINGLE-LEVER ANALYSIS OF ENAS AND DARTS
In this section we apply our analysis to understanding two existing NAS algorithms, ENAS (Pham al., 2018) and DARTS (Liu et al., 2019). For simplicity, we assume objectives induced by architec- tures in the relaxed search space are 7-smooth, which excludes components such as ReLUU. However, such cases can be smoothed via Gaussian convolution, i.c. adding noise every gradient; thus given the noisiness of SGD training we believe the following analysis is still informative (Kleinberg et al., 2018).
ENAS continuously relaxes A via neural controller that samples architectures A. so θ RO()"), where h is the number of hidden units. The controller is trained with Monte Carlo gradients On the other hand, first-order DARTS uses a mixture relaxation similar to the one Section A but using softmax instead of constraining parameters the simplex. Thus @ R | for E the set of learnable edges and O the set of possible operations. we assume that both algorithms use SGD for the architecture parameters then compare them we interested in their respective values of Gg. which we will refer to as GenAS and GDARTS. Before proceeding, we note again that our theory holds only for the single-level objective and when using SGD as the architecture optimizer, whereas both algorithms specify the bilevel objective and Adam (Kingma & Ba, 2015), respectively.
At very high level, the Monte Carlo gradients used by ENAS are known be high-variance, so GENAS may be much larger than GDARTS, yielding faster convergence for DARTS, which is reflected in practice (Liu al., 2019). We can also do a simple low-level analysis under the assumption that all architecture gradients are bounded entry-wise, i.e. in f -norm, by some constant; then since the squared f2-norm bounded by the product of the dimension and the squared -nom we have GENAS = ((h2) while GARTS ((E))) Since ENAS uses hidden state size of h 100 and the DARTS search space has E = 14 edges and |O| = operations, this also points to DARTS needing fewer iterations converge.
18

---

Published as a conference paper at ICLR 2021
C EXPERIMENTAL DETAILS
We provide additional detail on the experimental setup and hyperparameter settings used for each benchmark studied in Section 4. We also provide more detailed discussion of how XNAS differs from GAEA, along with empirical results for XNAS on the NAS-Bench-201 benchmark.
C.I DARTS SEARCH SPACE
We consider the same search space as DARTS (Liu et al., 2019), which has become one of the standard search spaces for CNN cell search (Xie et al., 2019; Nayman et al., 2019; Chen et al., 2019; Noy et al., 2019; Liang al., 2019). Following the evaluation procedure used in Liu et al. (2019) and Xu et al. (2020)..
evaluation of GAEA PC-DARTS consists of three stages:
Stage 1: In the search phase, we rum GAEA PC-DARTS with random seeds to reduce variance from different initialization of the shared-weighn network.
Stage 2: We evaluate the best architecture identified by each search run by training from scratch.
Stage We perform more thorough evaluation of the best architecture from stage 2 by training with ten different random seed initializations.
For completeness, we describe the convolutional neural network search space considered. cell consists of 2 input nodes and 4 intermediate nodes for total of 6 nodes. The nodes ordered and subsequent nodes can receive the output of prior nodes as input so for a given node k, there are k 1 possible input edges node Therefore, there total of 3 + 4 + 5 14 edges in the weight-sharing network.
An architecture is defined by selecting 2 input edges per intermediate node and also selecting single operation per edge from the following operations: (1) 3 x 3 separable convolution, (2) 5 x separable convolution, (3) x 3 dilated convolution, (4) 5 dilated convolution, (5) max pooling, (6) average pooling, (7) identity (8) zero. We use the same search space to design "normal" cell and a "reduction" cell; the normal cells have stride operations that do not change the dimension of the input, while the reduction cells have stride 2 operations that half the length and width dimensions of the input. In the experiments, for both cell types, after which the output of all intermediate nodes concatenated to form the output of the cell.
C.1.1 STAGE 1: ARCHITECTURE SEARCH
For stage 1, as is done by DARTS and PC-DARTS, we use GAEA PC-DARTS to update architecture parameters for smaller thared-weight network the search phase with 8 layers and 16 initial channels. All hyperparameters for training the beight-sharing network are the same as that used by PC-DARTS:
train:
scheduler: cosine
Ir_anneal_cycles: 1
mmocth__rossseetroppe false batch_size: 256
learning_rate: 0.1
learning_rate_mnnn 0.0
momentum: 0.9
weight_decay: 0.0003
init_channels: 16
layers:
autoaugment: false cutout: false
auxiliary: false
0
grad_clip:
Note (Liu et al., 2019) trains the weight-sharing network with 4 random seeds. However, since PC-DARTS significantly faster than DARTS, the cost of additional seed is negligible.
19

---

Published as a conference paper at ICLR 2021
For GAEA PC-DARTS, initialize the architecture parameters with equal weight across all options (equal weight across all operations per edge and equal weight across all input edges per node). Then, train the shared-weights network for 10 epochs without performing any architecture updates to warmup the weights. Then, we use a learning rate of 0.1 for the exponentiated gradient update for GAEA PC-DARTS.
C.1.2 STAGE 2 AND 3: ARCHITECTURE EVALUATION
For stages 2 and 3, we train each architecture for 600 epochs with the same hyperparameter settings as PC-DARTS:
train:
scheduler: cosine
lr_anneal_oycles: smooth__rosssentrroyy. false batch_size: 128
Learning_rate: 0.025
learning_rate_min: 0.0
momentum: 0.9
weight_decay: 0.0003
init_channels: 36
layers: 20
autoaugment: false cutout: true cutoout_lenghh: 16
auxiliary: true auxiliary_weightz 0.4
drop_path_prob: 0.3 grad_clip:
C.1.3 BROAD REPRODUCIBILITY
Our 'broad reproducibilityy results in Table show the final stage evaluation performance of GAEA PC-DARTS for 2 additional sets of random seeds from stage search. The performance of GAEA PC-DARTS for one set is similar that reported in Table 1, while the other is on par with the performance reported for PC-DARTS in Xu et al. (2020). We do observe non-negligible variance in the performance the architecture found by different random seed initializations of the shared-weighh network, necessitating running multiple searches before selecting architecture. We also found that it was possible to identify and eliminate poor performing architectures in just 20 epochs of training during stage 2 intermediate evaluation, thereby reducing the total training cost by over 75% (we only trained 3 out of 10 architectures for the entire 600 epochs).
Stage 3 Evaluation
Set (Reported) 2.50 + 0.07
Set 2 2.50 + 0.09
Set 3
2.60 + 0.09
Table 3: GAEA PC-DARTS Stage 3 Evaluation for sets of random seeds.
We depict the top architectures found by GAEA PC-DARTS for CIFAR-10 and ImageNet in Figure and detailed results in Tables 4 and 5.
20

---

Published as a conference paper at ICLR 2021
Test Ervor
Params (M)
Search Cost
Comparable Search Space
Search
Architecture
Best
Average
(GPU Days)
Method
Sbake-Sbake (DeVries Taylor, 2017)
N/A
2.56
26.2
PyramidNet (Yanadu al., 2018)
2.31
NAA
26
manual
NASNec-AA (Zoph sl., 2018)
NIA
2.65
3.3
2000
RL
AmoobaNettB" (Real et 2019)
N/A
2.55 +: 0.05
2,8
3150
evolation
ProxylesNNAS (Cai 2019)
2,08
N/A
5.7
gradient R1.
ENAS (Pham et al., 2018)
2.89
N/A
4.6
0.5
Random search wst (Li Taalalkarr 2019)
2.71
2.85 0.08
3.8
0.7
random
ASNG NAS (Akimoto
2019)
NIA
2.83 1: 0.14
3.9
0.1
gradient
SNAS (Xie et 2019)
N/A
2.85 + 0.02
2.8
1.5
gradient
DARTS (Ist-orderj) (Liu el al., 2019)
N/A
3.00
0.14
3.3
gratient
onder)
(Liu (
al., 2019)
gradient
PDARTS# (Chen
3.4
gradieut
PC-DARTS' (Xu et 2020)
N/A
2.57
0.07
3.6
gradient
GAEA PC-DARTS' (Ours)
2.39
2.50 + 0.06
3.7
0.1
gradient
comparable number parameters. For fair comparison other work, show the seurch cost for training shared weights network with single initialization.
We show results for networks
Scarch space and backhone architecture (PyramidNet) differ from the DARTS setting.
results not reported multiple seeds. Additionally. PDARTS deeper weighhtshariie networks during search, which PC-DARTS has also been shown to improve performance (Xu al., 2020), so we GAEA PC-DARTS further improve if modified similarty.
Table 4: DARTS (CIFAR-10):
Comparison with manually designed networks and those found by SOTA NAS methods, mainly the DARTS search space (Liu al., 2019). Results grouped by the type of search method: manually designed, full-evaluation NAS, and weight-sharre NAS. All test eπrors are for models trained with auxiliary towers and cutout (parameter counts exclude auxiliary weights). Test errors we report are averaged over 10 seeds. "_" indicates that the field does not apply while "N/A" indicates unknown. Note that search cost is hardwareedeeenddett our results used Tesla V100 GPUs.
Test Error
Params
Search Cost (GPU Days)
Search
Architettre
Source
top-1
top-5
(M)
Method
MohileNet
(Howard 2017)
10.5
munual
ShuffleNet V2
(Ma et al., 2018)
25.1
N/A
~
manual
NASNet-A
(Zoph et al., 2018)
26.0
5.3
1800
RL
Cm
(Real et al., 2019)
24.3
6.4
3150
evolution
DARTS
(Liu et al., 2019)
26.7
4.7
gradient
SNAS
(Xic et al., 2019)
27.3
9.2
4.3
1.5
gradient
ProxyeesNNAS
(Cai et al., 2019)
24.9
7.5
7.1
8.3
gradient
PDARTS
(Chn et al., 2019)
24.4
4.9
gradient
(CIFAR-IO) 10)
2020)
gradient
PC-DARTS (ImageNet)*
(Xu 2020)
24.2
5.3
gradient
GAEA PC-DARTS (CIFAR-10)*
Ours
24.3
5,3
gradient
GAEA PC-DARTS (ImageNer)
Ours
24.0
7.3
5.6
3.8
gradient
F.,... See notes in Table 4.
Table 5: DARTS (ImageNet): Comparison with manually designed networks and those found by SOTA NAS methods, mainly the DARTS search space (Liu et al., 2019). Results are grouped by the type of search method: manually designed, full-evaluation NAS, and weight-sharing NAS. All test errors for models trained with auxiliary towers and cutout but no other modifications, e.g. label smoothing (Müller et al., 2019), AutoAugment (Cubuk al., 2019), Swish (Ramachandran al., 2017), squeeze and excite modules (Hu al., 2018), etc. ". indicates that the field does not apply while "N/A" indicates unknown. Note that search cost is dareeen:-dependent; our results used Tesla V100 GPUs.
21

---

Published as a conference paper at ICLR 2021
c_(k-2)
sep_conv__t
skip_cue hip_connect
syp_conv33x3
dil_conv_St 3x3
sep_conv_3e
skip_commn coip_coneet
2
c_(k)
c_(k-1)
sep conv 3x3
sep cal_conv____ ___3
(a) CIFAR-10: Normal Cell
sep_comv 5x55
max poc_ppoo__30
5x5
dil _cooo__3333
sep.ccmmv 55.5
c__
max, moo_ 3x3
cony
cop_ 3x.3
[k
(b) CIFAR-10: Reduction Cell
sep_conv cony 3x3
sep_conv_ _x5
c (k-2)
skip connect
sep_conv_
skip_connect
sep cony 5x5
C [k]
c_(k-1
sep_conv 3x3
sep_conv_3xe
(c) ImageNet: Normal Cell
c. (_(k-2)
sep_conv _333
dil_conv_55xt
max max_pool____ poop_oooo 1_x3
max_ max_pool___ pool_3x3 _33
sep conv 5x5
[kk
sep hop_coov_300
c c_(k-1)
sep_conv 3x.
2
sep conv _ _55
3
(d) ImageNet: Reduction Cell
Figure 3: The best normal and reduction cells found by GAEA PC-DARTS on CIFAR-10 (top) and ImageNet (bottom).
22

---

Published as a conference paper at ICLR 2021
CIFAR10: DARTS (1st Order)
CIFARIOD: DARTS (1st Order)
IMAGENET16-122 DARTS (1st Order)
76-
60-
40-
50-
Gladl
23-
20-
20-
25
10-
Epochs
Epechs
Epochs
CIFARIO: (ERM)
(ERM)
IMAGENETIG-122 GAEA DARTS (ERM)
Obedte Teat Acc
70
Cracle Text
35.0
32.5
42
27.5
Epochs
Epochs
CIFAR10:
(bilevel)
CIFAR100: (bilevel)
IMAGENETI6 120: (bllevel)
94.
68-
72-
Obeche Text Ace
21-
Gracte Texl
76-
68-
91-
92-
Epochs
Epechs
Spechs
Figure 4: NAS-Bench-2011 Learning Curves. Evolution over search phase epochs of the best archi- tecture according to the NAS method. DARTS (first-order) converges to nearly all skip connections while GAEA is able to suppress overfitting to the mixture relaxation by encouraging sparsity in operation weights.
C.2 NAS-BENCI--SSIOTI
The NAS-Bench-
subsets of the Berch--Shoot Shotl benchmark (Zela al., 2020a) contains 3 different search spaces that are 101 search space. The search spaces differ the number of nodes and the number of input edges selected per node. We refer the reader (Zela et al., 2020a) for details about each individual search space.
Of the NAS methods evaluated in Zela al. (2020a), PC-DARTS had the most robust performance across the three search spaces and converged to the best architecture search spaces and 3. GDAS, a probabilistic gradient NAS method, achieved the best performance on search space Hence, we focused on applying geometry-awa approach to PC-DARTS. We implemented GAEA PC- DARTS within the repository provided by the authors of Zela al. (2020a) available https: / //github. com/ hut//auton oml wtt////ttto///sseeeehtt.t wwwsennhh-sshhtteeee training the weight-sharing network as that used by Zela al. (2020a) for PC-DARTS. Similar to the previous benchmark, we initialize architecture parameters to allocate equal weight to all options. For the architecture updates, the only hyperparameter for GAEA PC-DARTS is the learning rate for exponentiated gradient, which we set to 0.1.
We used the same hyperparameter settings for
As mentioned Section 4, the search spaces considered in this benchmark differ in that operations are applied after aggregating all edge inputs node instead of per edge input in the DARTS and MAS--Bechh-211 search spaces. This structure inherently limits the size of the weight-sharing network scale with the number of nodes instead of the number of edges (O(Inodes])) ))). thereby limiting the degree of overparameterizzatin. Understanding the impact of overparameterizztion on the performance of weight-sharing NAS methods is direction for future study.
23

---

Published as a conference paper at ICLR 2021
C.3 NAS-BENCH-20
The NAS-Bench-2DD benchmark (Dong & Yang, 2020) evaluates a single search space across 3 datasets: CIFAR-IO, CIFAR-I00, and miniature version of ImageNet (ImageNet-16-122 ImageNet-16- 22 is a downsampled version of ImageNet with 16 x 16 images and 120 classes for total of 151.7k training images, 3k validation images, and 3k test images. The authors of Dong & Yang (2020) evaluated the architecture search performance of multiple weight-sharing methods and traditional hyperparameter optimization methods on all three datasets. According to the results from Dong& & Yang (2020), GDAS outperformed other weight-sharing methods by large margin. Hence, we first evaluated the performance GAEA GDAS on each of the three datasets. Our implementation of GAEA GDAS uses an architecture learning rate of 0.1, which matches the learning rate used for GAEA approaches in the previous two benchmarks. Additionally, we run GAEA GDAS for 150 epochs instead of 250 epochs used for GDAS in the original benchmarked results; this is why the search cost is lower for GAEA GDAS. All other hyperparameter settings are the same. Our results for GAEA GDAS is comparable to the reported results for GDAS CIFAR-10 10 and CIFAR-100 100 but slightly lower on ImageNet- 16-1 10.. Compared to our reproduced results for GDAS, GAEA GDAS outperforms GDAS on CIFAR-100 and matches it on CIFAR-I0 10 and ImageNet-16-120.
Next, to see if we can use GAEA to further improve the performance of weight-sharing methods, we evaluated GAEA DARTS (first order) applied both the single-level (ERM) and bi-level optimization problems. Again, we used a learning rate of 0. and trained GAEA DARTS for 25 epochs on each dataset. The one additional modification we made was exclude the zero operation, which limits GAEA DARTS to subset of the search space. To isolate the impact of this modification, we also evaluated first-order DARTS with this modification. Similar to (Dong & Yang, 2020), we observe DARTS with this modification to also converge to architectures with nearly all skip connections, resulting in similar performance as that reported in Dong & Yang (2020). We present the learning curves of the oracle architecture recommended by DARTS and GAEA DARTS (when excluding zero operation) over the training horizon for 4 different runs in Figure 4. For GAEA GDAS and GAEA DARTS, we train the seight-sharing network with the following hyperparameters:
train:
scheduler: cosine
tr_anneal_cycles: 1
smooth__rosssentrron false batch_size: 64
learning_rate: 0.025
learning_rate_min min: 0.001
momentum: 0.9
weight_decay: 0.0003
init_channels: 16
layers:
autoaugment: false cutout: false
auxiliary: false auxiliary_weight: 0.4
drop_path_prob: 0 grad_clip:
Surprisingly, we observe single-level optimization yield better performance than solving the bi- level problem with GAEA DARTS on this search space. In fact, the performance of GAEA DARTS (ERM) not only exceeds that of GDAS, but also outperforms traditional hyperparameter optimization approaches on all three datasets, nearly reaching the optimal accuracy on all three datasets. In contrast, GAEA DARTS (bi-level) outperforms GDAS on CIFAR-100 and mmageNet-16-135 but underperforms slightly on CIFAR-10. The single-level results on this benchmark provides concrete support for our convergence analysis, which only applies to the ERM problem. As noted in Section 4, the search space considered in this benchmark differs from the prior two in that there is no subsequent edge pruning. Additionally, the search space is fairly small with only 3 nodes for which architecture decisions must be made. The success of GAEA DARTS (ERM) on this benchmark indicate the need for a better understanding of when single-level optimization should be used in favor of the default bi-level optimization problem and how the search space impacts the decision.
24

---

Published as a conference paper at ICLR 2021
CIFARIO: XNAS
CIFARIOD: XNAS
IMAGENETIE MANEETT6622000000 XNAS
20
Ohatle Text Are
Ace
50-
43.2
60-
70-
20-
10-
Epochs
Epochs
Figure 5: NAS-Bench-201: XNAS Learning Curves. Evolution over search phase epochs of the best architecture according 4 runs of XNAS. XNAS exhibits the same behavior DARTS and converges to nearly all skip connections.
C.4 COMPARISON TO XNAS
As discussed in Section I, XNAS is similar to GAEA in that it uses exponentiated gradient update but is motivated from a regret minimization perspective. Nayman et al. (2019) provides regret bounds for XNAS relative the observed sequence of validation losses, however, this is not equivalent the regret relative to the best architecture in the search space, which would have generated a different sequence of validation losses.
XNAS also differs in its implementation in two ways: (1) a wipeout routine is used to zero out operations that cannot recover exceed the current best operation within the remaining number of iterations and (2) architecture gradient clipping is applied per data point before aggregating to form the update. These differences are motivated from the regret analysis and meaningfully increase the complexity of the algorithm. Unfortunately, the authors do not provide the code for architecture search in their code release https: //gi thub. com/N NN yNayman/ XNAS. Nonetheless, we implemented XNAS for the
201 search space to provide point of comparison to GAEA.
Our results shown in Figure 5 demonstrate that XNAS exhibits much the same behavior as DARTS in that the operations all converge to skip connections. We hypothesize that this is due to the gradient clipping, which obscures the signal kept by GAEA in favor of convolutional operations.
25


Reviews:
[{"review_id": "xV6KPHQkNn", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces the geometry-aware framework that can be adapted to any existing weight-sharing NAS methods optimized over gradient descent. The authors focus on the aspect of optimizing the architecture parameters to overcome the criticism of weight-sharing methods. The author's method relies on the mirror descent supporting their methods with a theoretical guarantee for the fast convergence. The author also supports their methods on various datasets such as CIFAR-10, ImageNet, NAS-Bench-201 (Dong & Yang), and NAS-Bench-1Shot (Zela et al.).\n\nThe paper supports their ideas not only supported by theoretical background, but outperforming results consistently with extensive empirical experiments such as CIFAR-10, ImageNet, NAS-Bench-1Shot1, and NAS-Bench-201. Furthermore, the GAEA can easily be applied to existing NAS methods which I believe making this work more valuable. \n\nStrength\n1. Their methods easily apply to existing NAS methods with gradient-based methods. \n2. Theoretically supported methods with convergence guarantee. \n3. Extensive empirical experiments on CIFAR-10, ImageNet, NAS-Bench-1Shot1, and NAS-Bench-201. Moreover, detailed experiment descriptions and fair setups that are critical in NAS comparison are provided.\n4. Novel perspective of view (optimization perspective) to overcoming the weight-sharing methods' criticism of recent works. \n5. Reproducible code included along with the paper. \n\nOverall, I recommend clear acceptance. This paper will provide new insights/perspective to NAS algorithms which adopts weight-sharing methods. \n\nReference\n1. Dong & Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search (ICLR 2020)\n2. Zela et al. NAS-Bench-1Shot1: Benchmarking and Dissecting One-Shot Neural Architecture Search (ICLR 2020)", "extra_scores": {}, "extra_text": {}}, {"review_id": "NXPecoAyuyU", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Pros:\n1.\tThis paper gives a proof of finite-time convergence, which is the first paper working on this. Besides, the paper gives corresponding analysis of ENAS and DARTS. This is a new perspective of NAS methods.\n2.\tThis work uses EG method to update architecture parameter, which takes the advantage of EG method and is reasonable to be applied on NAS problem.\n3.\tThe experiment results show the efficiency and effectiveness of the proposed method.\n\nCons:\n1.\tUsing EG to update architecture parameters can only accelerate convergence, which has nothing to do with improving the NAS performance. It is still confusing that why single-level optimization can resolve rank disorder and poor performance. It is not clear that the slight improvement on the performance is due to your algorithm or accident.\n2.\tEfficiency is claimed as an important point in this paper. However, only the results in Table 2 shows GAEA shorten the time cost. In Table 1, it cannot be detected that your method is more efficient. Is that because updating architecture parameters does not cost too much time in these experiment? If so, the contribution may be less.\n3.\tIn Figure 2, it is not easy to detect the performance difference between your method and the baseline. You should also explain the meaning of lines with deeper colors.\n4.\tIt is better to add discussion or conclusion at the end of your paper, which can help readers to better understand your work.\n\nOverall Review:\nThis paper gives a theory about the convergence time of NAS methods, which provides new perspectives on NAS problem. The paper find that EG method is appropriate on updating architecture parameters and this method can improve the efficiency of NAS problem. There are also some questions mentioned above in this paper. With some modifications, this paper could be an excellent paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9GFhxyhsYay", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe submission presents a modification to the DARTS family of efficient Neural Architecture Search algorithms. The authors claim their modification (i) leads to better empirical performance, and (ii) is theoretically well-motivated. DARTS is a Neural Architecture Search algorithm which aims to find the most accurate network architecture within a human-defined search space.\n\nThe original DARTS algorithm uses gradient descent to optimize both (i) a set of shared model weights $\\mathbf{w}$ which are used to rank different candidate architectures within a search space and (ii) a vector $\\theta \\in \\mathbf{R}^n$ which corresponds to a continuous (real-valued) relaxation the network architecture. At the end of the search, $\\theta$ is converted into a discrete architecture within the search space; this architecture is the output of the search process. The authors' proposed variant of DARTS -- which they call GAEA (Geometry-Aware Gradient Algorithm) -- updates the architectural parameters $\\theta$ using *exponentiated* gradient descent instead of standard gradient descent. (Details are provided in Equation (8) in Section 3.3 of their paper, but the modification seems straightforward to implement.) The authors claim this modification favors sparse values of $\\theta$, and helps decrease the gap between discrete architectures and their continuous relaxations.\n\nOn the applied side: The authors evaluate efficient NAS algorithms with and without their modification on three different benchmark tasks. On two of the tasks, the performance of their modified algorithm seems quite close to that of a baseline without the modification. On the third task (NASBench-201), the improvements appear to be quite substantial in one case. In most (but not all) cases, the authors directly compare the results of architecture searches obtained with and without their proposed modification. This type of control experiment is important and very helpful for a NAS paper, since it makes it possible to directly quantify the helpfulness of the proposed changes.\n\nOn the theoretical side: I had trouble understanding the significance of the authors' theoretical results. In particular: the paper claims to prove stationary-point convergence bounds for a variant of their algorithm but doesn't explain what stationary-point convergence means or why it's important. I'm very much on the applied side of machine learning, so it's possible that someone with a stronger theory background would get more out of the theoretical results. However, I also think the theoretical results could be much better-explained than they currently are. (I read through Section 3, but have not tried to check the theoretical results carefully.)\n\n*Pros:*\n* Paper provides experiments on three different benchmark tasks, and reports results for multiple NAS algorithms (mostly based on DARTS).\n* Strong empirical results for some of the NASBench-201 experiments.\n* Paper appears to provide solid baselines for most experiments.\n* Proposed approach is not overly complex, and seems straightforward to implement.\n\n*Cons:*\n* Novelty is limited, since the authors are proposing a relatively limited change to an existing family of Efficient NAS algorithms. (This would, however, be a non-issue if the proposed changes were effective enough.)\n* Unclear presentation of theoretical results.\n* Quality improvements seem quite limited on 2 of the 3 benchmark tasks. (Part of the problem might -- as the authors suggest -- be due to limited headroom.)\n* For the benchmark task with the largest improvement -- NASBench-201 -- the authors only provide their own baseline for 1 of the 3 NAS algorithms they evaluate, and for this variant (GDAS), the improvements over the baseline are quite small. So it's not clear to me how much of the improvements for the other two algorithms can be attributed to GAEA and how much can be attributed to NAS setups that are better tuned than the ones from the original NASBench-201 paper.\n\n## Notes on Experimental Evaluation\nThe abstract makes a strong claim about the quality improvements brought about by the authors' proposed modification, so I'll evaluate the paper relative to that claim: \"we exceed the best published results for both CIFAR and ImageNet on both the DARTS search space and NAS-Bench-201; on the latter we achieve near-oracle-optimal performance on CIFAR-10 and CIFAR-100.\"\n\nThe submission evaluates their method on three tasks: (i) the search space from the DARTS paper, (ii) the NASBench-1shot1 benchmark task, and (iii) the NASBench-201 benchmark task. On the plus side: the authors appear to provide direct comparisons between DARTS-based NAS algorithms with and without their proposed GAEA modifications (although this requires some confirmation of details which are currently missing from the paper). On the minus side: the improvements of GAEA algorithms over their non-GAEA equivalents seem quite small in most cases. (The authors attribute this to limited headroom in the search spaces, which seems plausible to me.)\n\nOn the original DARTS search space, the authors' proposed GAEA PC-DARTS algorithm produces architectures with an average test error rate of 2.50%, compared with 2.57% for standard PC-DARTS. The authors do not provide numbers for their own reproduction of the original PC-DARTS results; the writing implies that the hyper-parameters and search space are comparable. Providing numbers for the authors' reproduction of PC-DARTS would strengthen these results. Assuming the current numbers are in fact comparable: the performance improvements appear to be extremely small, and are probably within the range of statistical error.\n\nOn the NASBench-1shot1 search space, the authors claim that their proposed GAEA PC-DARTS algorithm works slightly better than an unmodified PC-DARTS, although the improvements appear to be small. While this seems reasonable given the data they provided, I think the presentation of results can be improved; the results presented in Figure 2 are difficult for me to interpret because the plots are visually noisy and contain many overlapping lines of different colors.\n\nNASBench-201 is the most interesting (and potentially most appealing) case. The authors provide accuracy numbers for both their reproduction of the existing GDAS algorithm and their proposed GAEA-GDAS variant, and performance of the two seems quite similar (e.g., 93.55% test accuracy on CIFAR-10 for GDAS-GAEA compared with 93.52% for GDAS). The gap is larger on CIFAR-100, but primarily because the authors' reproduction of GDAS has lower accuracy than the published GDAS numbers from the NASBench-201 paper. For other DARTS variants, the accuracy improvements are quite impressive (e.g., 94.10% accuracy for GAEA-DARTS-ERM), but the authors do not provide a non-GAEA baseline for this configuration. Furthermore, the accuracies that the original NASBench-201 paper provides for baselines such as ENAS and DARTS are extremely low, so I think that providing a careful reproduction of DARTS-ERM with properly tuned hyper-parameters would help make the results more convincing.\n\n## Notes on Clarity\nWhile the paper seems reasonably well-organized and well-proofread, I found parts of it difficult to understand. I had trouble understanding Section 3 (which presents the paper's main theoretical results) in particular. The section is notation and terminology-heavy, and would be easier to follow if it spent more time explaining relevant terms.\n\nI found Table 1 difficult to interpret because different rows of the table contain the results of architecture searches performed using different search spaces and/or model training hyper-parameters. For example, ProxylessNAS uses a very different search space than PC-DARTS and GAEA PC-DARTS. While the authors note this particular example in the text under the table, the table would be much easier to interpret if it was organized to show which subsets of the results were comparable to each other (i.e., used the same model training hyper-parameters and search space).\n\nI also had trouble understanding Figure 2, which contains 8-10 overlapping red/blue lines. I also had trouble understanding the relationship between the \"PC-DARTS\" and \"Best from Zela et al.\" lines (since Zela et al. evaluate PC-DARTS in their paper). It would be helpful to clarify the distinction between the two.\n\n\n## Additional Notes\n\nI had trouble understand this sentence from the end of Section 2.2: \"Furthermore, for methods that adapt architecture parameters during search, it [using a first-order method] makes clear that we need not worry about rank disorder as long as we can optimize and generalize\"\nWhy don't first-order methods need to worry about rank disorder? This needs to be better explained.\n\nIn Equation (5), what does the $\\bigodot$ symbol denote? My best guess is that it refers to an elementwise product, but it would be helpful to state the meaning more clearly.\n\nIn Section 3.2: It's not clear to me what the significance of Theorem 1 is in practice. What is the significance of having a small expected value for $\\Delta$ or of being close to an approximate stationary point? What does it mean, and why is it desirable? This needs to be better-explained.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a solid paper providing the first theoretical convergence result for NAS and showing promising empirical results.
The authors' proposed GAEA method can be combined with different types of weight-sharing algorithms (DARTS, PC-DARTS, etc) and is likely to reduce the impact of the architecture discretization step due to finding sparser solutions.
I clearly recommend acceptance and would expect this to make a nice spotlight.
Decision: Accept (Spotlight)