On Weight-Sharing and Bilevel Optimization in Architecture Search
Authors: Mikhail Khodak
Liam Li
Maria-Florina Balcan
Ameet Talwalkar
Venue:  (2020)
Keywords: neural architecture search
weight-sharing
bilevel optimization
non-convex optimization
hyperparameter optimization
model selection

Abstract: Weight-sharing—the simultaneous optimization of multiple neural networks using the same parameters—has emerged as a key component of state-of-the-art neural architecture search. However, its success is poorly understood and often found to be surprising. We argue that, rather than just being an optimization trick, the weight-sharing approach is induced by the relaxation of a structured hypothesis space, and introduces new algorithmic and theoretical challenges as well as applications beyond neural architecture search. Algorithmically, we show how the geometry of ERM for weight-sharing requires greater care when designing gradient- based minimization methods and apply tools from non-convex non-Euclidean optimization to give general-purpose algorithms that adapt to the underlying structure. We further analyze the learning-theoretic behavior of the bilevel optimization solved by practical weight-sharing methods. Next, using kernel configuration and NLP feature selection as case studies, we demonstrate how weight-sharing applies to the architecture search generalization of NAS and effectively optimizes the resulting bilevel objective. Finally, we use our optimization analysis to develop a simple exponentiated gradient method for NAS that aligns with the underlying optimization geometry and matches state-of-the-art approaches on CIFAR-10.

Under review as a conference paper at ICLR 2020
ON WEIGHT-SHARING AND BILEVEL OPTIMIZATION IN ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Weight-sharing-uhhe simultaneous optimization multiple neural networks using the same parameters has emerged as a key component of state-of tate-offthhe-at neural architecture search. However, its success poorly understood and often found to be surprising. We argue that, rather than just being an optimization trick, the weight-sharing approach induced by the relaxation of structured hypothesis space, and introduces new algorithmic and theoretical challenges well as appli- cations beyond neural architecture search. Algorithmically, we show how the ge- ometry of ERM for weight-sharing requires greater care when designing gradient- based minimization methods and apply tools from non-convex non- -on-Euclidean op- timization to give general-po purppas- algorithms that adapt the underlying struc- ture. We further analyze the learning-theoredn behavior of the bilevel optimization solved by practical weight-sharing methods. Next, using kernel configuration and NLP feature selection as case studies, we demonstrate how weight-sharing applies the architecture search generalization of NAS and effectively optimizes the re- sulting bilevel objective. Finally, we use our optimization analysis to develop a simple exponentiated gradient method for NAS that aligns with the underlying optimization geometry and matches state-of- -fie-oofthhearr approaches on CIFAR-10 10.
INTRODUCTION
Weight-sharing neural architecture search (NAS) methods have achieved state-of-the-art perfor- mance while requiring computation training of just a single shared-weights network (Pham et al.) 2018 Li and Talwalkar 2019; Liu et al., 2019). However. weight-sharing remains poorly under- stood. In this work, we present novel perspective on weight-sharing NAS motivated by the key observation that these methods subsume the architecture hyperparameters as another set of learned parameters of the shared-wer weightt network, in effect extending the hypothesis class. An important ramification of this insight is that weight-sharing is not NAS-specific and can be used to tune hy- perparameters corresponding to parameterized feature maps of the input data. We refer this larger subset of hyperparameter optimization problems as architecture search, and we study the following two questions associated with weight-sharing applied to the architecture search problem:
1. How can we efficiently optimize the objective induced by applying weight sharing to architecture search, namely minimizing empirical risk in the joint space of model and architecture parameters? For large structured search spaces that preclude brute force search, natural approach to architecture search with weight-sharing is to use gradient-based methods to minimize the empirical risk over a continuous relaxation of the discrete space (Liu et al., 2019). Although this has allowed NAS re- searchers to apply their preferred optimizers to determine architecture weights, it is far from clear that the success of established methods for unconstrained optimization in training neural networks will naturally extend to these constrained and often non-Euclidean environments. As we foresee that architecture search spaces will continue become more complex and multi-faceted, we ar- gue for and develop more principled, geometry-aware formulation of the optimization problem. Drawing upon the mirror descent meta-algorithm (Beck and Teboulle (003)) and successive convex approximation, we give non-asymptotic stationary-poiin convergence guarantees for the empirical risk minimization (ERM) objective associated with weight-sharing via algorithms that simultane- ously connect to the underlying problem structure and handle the alternating block nature of the architecture search. Our guarantees inform the design of gradient- based weight-sharing methods by explicitly quantifying the impact of optimizing in the right geometry on convergence rates.

---

Under review as a conference paper at ICLR 2020
2. What are the generalization benefits of solving a bilevel optimization for the architecture search problem commonly considered in practice? At its core, the goal of architecture search is to find a configuration that achieves good generalization performance. Consequently, a bilevel objective that optimizes the architecture weights using a separate validation loss is commonly used in practice in lieu of the ERM objective naturally induced by weight sharing (Pham et al.] 2018 Liu et al. 2019 Cai et al. 2019). The learning aspects of this approach have generally been studied in settings with much stronger control over the model complexity (Kearns et al., 1997). We provide generaliza- tion guarantees for this objective over structured hypothesis spaces associated with finite set of architectures: this leads to meaningful bounds for simple feature map selection problems as well as insightful results for the NAS problem that depend on the size of the space of global optima.
To validate our theoretical results, we conduct empirical studies of weight-sharing in two settings: (1) shallow feature map selection, i.e., tuning the hyperparameters of kernel classification and NLP featurization pipelines, and (2) CNN neural architecture search. In (1) we demonstrate that weight- sharing efficiently optimizes the bilevel objective and achieves low generalization error with respect to the best architecture setting. For (2), motivated by insights from our convergence analysis, we develop simple exponentiated gradient version of DARTS (Liu et al., 2019) called EDARTS that better exploits the geometry of the optimization problem. We evaluate EDARTS on the design of CNN architectures for CIFAR-10 and demonstrate that EDARTS finds better architectures than DARTS in less than half the time. We also achieve very competitive results relative to state-of-the-art architectures when using an extended evaluation routine.
Related Work: Our work on optimization for weight-sharing benefits from the literature on first- order stochastic optimization (Hazan and Kale| 2014 Beck 2017) and in particular the mirror de- scent framework (Beck and Teboulle [003). Specifically, we use successive convex approxima- tion (Razaviyayn et al.) 2013] Mairal 2015) to show convergence of alternating minimization and derive geometry-depndder
rates comparable to existing work on non-convex stochastic mirror de- scent (Dang and Lan 2015] Zhang and He 2018). Our result generalizes to the constrained, non- Euclidean, and multi- block setting an approach of AAgawal et al. (2019) for obtaining non-convex convergence from strongly convex minimization, which may be of independent interest. Previous optimization results for NAS have generally only shown bounds on auxiliary quantities such gret that are not well-connected to the learning objective (Noy et al. 2019 Nayman et al.) 2019] Carlucci al. 2019) have only given monotonic improvement or asymptotic guarantees (Aki- moto et al. [2019] Yao et al.] a119)019.. However, due to the generality of mirror descent, the approaches in the middle three papers can be seen special cases of our analysis. Finally, our analysis of the properties of the bilevel optimization is related to work on model selection (Vuong) 1989 Kearns al. 1997). but does not consider the configuration parameters as explicit controls on the model complexity. Our learning results are broadly related to hyperparameter optimization, although most work focuses on algorithmic and not statistical questions (Li et al. 2018 Kandasamy et al. 2017).
THE WEIGHT- SHAHHNG LEARNING PROBLEM
In this section, we formalize the weight-sharing learning problem, relate it to traditional ERM, and provide examples for the case of NAS and feature map selection that we use for the rest of the paper. Our main observation is that weight-sharing for architecture search extends the hypothesis space to be further parameterized by a finite set of configurations C. Formally, we have a structured
hypothesis space H(C, (Mle) X + Y: w W.c E C) over input space Z = X Y with induced hypothesis subclasses H. = (n x : w E W] parameterized by weights from W. The goal of learning is the usual one one-find (e) E HCC, W) with low population error ED ( = E( (x),.) y) for loss é: : Y x Y + RR. Hence, we can apply ERM as usual, with optional regularization, to select hypothesis from the extended hypothesis space; in fact this is done by some NAS methods (e.g.. Xie et al. 2019). The learning algorithm is then
min eeC
(T(())))) = min WEW.eEC
Σ (T.))T
E(Ml)) (a)) + Rw(w)= + Re(c)
(1)
for block specific regularizers Rw and Re. Note that in the absence of weight-sharing, we would
need to learn a separate hypothesis (())) for each hypothesis subclass H.. Although a brute force approach to selecting hypothesis from HCC, W) via ERM would in effect require this well,
2

---

Under review as a conference paper at ICLR 2020
subsequent examples demonstrate how the weight-sharing construct allows us to apply more efficient gradient- based optimization approaches, which we study in Section 3
Feature Map Selection: In this setting, the structure is induced by set of feature transformations so the hypothesis space is (o.( w E W, o E C} for some W Rd.. Examples of feature map selection problems include tuning kernel hyperparameters for kernel ridge classification and tuning NLP featurization pipelines for text classification. In these cases Jw a linear mapping (-) (w,-) and W C R".
{o; X + R" for = I...., , k),
Neural Architecture Search: Weight-sharing methods almost exclusively use micro cell-based search spaces for their tractability and additional structure (Pham et al. 2018 Liu al., 2019).
These search spaces can be represented as directed acyclic graphs (DAGs) with a set of ordered nodes N and edges E. Each node (0) in the DAG is a feature representation and each edge (fh-)) is an operation on the feature of node j passed to node and aggregated with other inputs to form x!f), with the restriction that given node j can only receive edges from prior nodes as input. Hence, the feature at a given node i is (+()) = Eje: olf-5) (z(11). Search spaces are then 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.
In this case the structure C C (0. 1 |i8i|o| of the hypothesis space is the set of all valid architectures for this DAG encoded by edge and operation decisions. 'rretting both weights w W and archi- tecture decision e E C as parameters, weight-sharing methods train a single shared-weights network h X + Y encompassing all possible functions within the search space. Therefore, the shared- weights network includes all possible edges between nodes and all possible operations per edges. In addition to the weights
W corresponding all the operations, the shared-weightt network also
takes architecture weights с E as input, where co (i.5) indicates the weight given to operation o on edge ji so that the feature of given node i is (1) Ej<s Eoco (1.5) (z..))
Gradient-basee weight-sharing methods apply continuous relaxations to the architecture search space in order compute gradients. Some methods like DARTS (Liu al.) 2019) and its vari- ants (Chen et al.; 2019; I Laube and Zell 2019, Hundt et al., 2019 Liang et al. 2019 Noy et al.) 2019 Nayman et al.[[2019) relax the search space by considering a mixture of operations per edge and then discretize to a valid architecture in the search space. With the mixture relaxation, we place all c E {0, 1} (ollo) in the above expressions by continuous counterparts A E [0, 1] with the constraint that Eoso 0.a-))
i.e., the architecture weights for operations on each edge sum to 1. Other methods like SNAS (Xie et al., 2019), ASNG-NAS (Akimoto et al. 2019). and Prox- ylessNAS (Cai et al., 2019) assume parameterized distribution pe from which architectures are sampled. By substituting continuous parameters 0 E @ in for discrete parameters c E C. we are able to use gradient-based methods to optimize (T) We address the question of how to effectively use gradient optimization for weight-sharing in the next section.
3 GEOMETRY-AWARE OPTIMIZATION WITH WEIGHT-SHARING
While continuous relaxation enables state-of-the-art results, architecture search remains expensive and noisy, with state-of-the-art mixture methods requiring second-order computations (Liu et al. 2019) and probabilistic methods suffering from high variance policy gradients (Xie et al. 2019) Moreover, while the use of SGD to optimize network weights is well-tested approach, architecture weights typically lie in constrained, non-Euclidean geometries in which other algorithms may be more appropriate. Recognizing this, several efforts have attempted to derive a better optimization schemes; however, the associated guarantees for most of them hold for auxiliary objectives, such as regret of local configuration decisions, that are not connected to the optimization objective (T) and ignore the two-block nature of the problem (Noy et al. 2019 Nayman et al. 2019, Carlucci et al., 2019). While/Akimol
al. (2019) do consider alternating descent method for the training objective, their results are asymptotic and certainly do not indicate any finite-time convergence.
In this section we address these difficulties by showing that the mirror descent (MD) framework [eeck and Teboulle, 2003) is the right tool for designing algorithms in the block optimization prob- lems that occur in architecture search. We describe how such geometry-awan gradient algorithms lead to faster stationary point convergence; as we will show in Section 5 this yields simple, princi- pled, and effective algorithms for large-scale multi-geometry problems such NAS.
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1:
Two geometry-aware optimization algorithms for multi- optimization for a
3-strongly-smene smooth function over X' x R, given associated DGFs wy : 2 + R.
Input: initialization z((1) X, batch-size N 2 1 (for SBMD), tolerance E > 0 (for ASCA) for iteration E [T]] do
sample ~ Uni and set
x (1+1) f- _
if SBMD Dang and Lan
2015 then
(t-1) arg min
(g. u) + WD., (ulla!") for g N Eド= 9. (x(2)) (15)
if ASCA (this work) then
2 (t-1)
t i
s.t. minee, min f(u) S for - f(.,
Output:
Unif Unif(2(0)7
Problem Geometry: We relax optimization problems of the form ① to the problem of minimizing function f X' + R over convex product space X' X X, consisting of blocks i, each with an associated norm || II()) For example, in typical NAS we can set X11 be the set-product of E simplices over the operations O and the associated norm to be || | while X2 W C Idd is the space of network weights and the associated norm is || [12. To each block i we further associate a distance- distance-generatiin function (DGF) w, : X + that is I-strongly-comee associated to a Bregman divergence Dw, (x1l)) (x) - wy(y) (Vwi x y). standard measure of distance (Bregman 1967). For example, in the Euclidean case using w2(+) = 1 1
w.r.t. || ll(): each
yields the usual squared Euclidean distance; over the probability simplex we often use the entropy wi (+) (+, log(-)), )) which is 1 I-strongly-convex w.r.t. |1-11ı and for which Dw., is the KL-divergence.
Given an unbiased gradient estimate g(z,, = V the (single- block) stochastic MD step is (g((r, (), u) + (u(l(a
Fe++1 arg min wEX
for some learning rate 1) > O. In the Euclidean setting this reduces to SGD, while with the entropic regularizer the iteration becomes equivalent to exponentiated gradient. Key to the guarantees for MD the fact that the dual norm of the problem geometry is used to measure the second moment of the gradient; if every coordinate of is bounded a.s. by a, then under Euclidean geometry the dependence is on (l]g(=) = (l]g(>))1 S o²d while using entropic regularization it is on El]g(=))] = Bl]g(=)] S o². Thus in such constrained é geometries mirror descent can yield dimension-free convergence guarantees. While in this paper focus the benefit in this simple case, the MD meta-algorithm can be used for many other geometries of interest in architecture search, such as for optimization over positive-definite matrices (Tsuda et al. 2005).
Algorithms and Guarantees: We propose two methods for the above multi-block optimization problems: stochastic block mirror descent (SBMD) and alternating successive convex approxima- tion (ASCA). At each step, both schemes pick a random coordinate i to update; SBMD then per- forms a mirror descent update similar to ( but with batched gradient, while ASCA optimizes a strongly-convex surrogate function using user-specified solver. Note that both methods require that f is (--ttroggly-smoote w.r.t. each block's norm Il()) to achieve convergence guarantees, a standard assumption in stochastic non-convex optimization (Dang and Lan 2015 Agarwal et al.) 2019). This condition holds for the architecture search under certain limitations, such as a restric- tion to smooth activations. In the supplement we also show that in the single-block case ASCA converges under the more general relative weakeeewwwkaaae coove-cyy criterion (Zhang and He 2018).
We first discuss SBMD, for which non-convex convergence guarantees were shown by Dang and Lan (2015); this algorithm is the one we implement in Section for NAS. A first issue is how to measure stationarity in constrained, set a smoothheess-deeendent constant À > O and measure how far the proximal gradient opera- tor proxV,(=) arg min x(V u) + (ull() is from fixed point, which yields the projected gradient measure [0]]2 = z (a)) Notably, in the unconstrained Euclidean
AnnFuulideann geometries. In the single-block setting we can
case this yields the standard stationarity measure [x)]]. For the multi-block case we replace (ullx) Eim Da (uilaaa and use the pseudo-norm ||a|| Ei || l2.. Then E X is
4

---

Under review as a conference paper at ICLR 2020
an e-stationary point of f w.r.t the projected gradient if [[Gx(z)] E. In the non-Euclidean case the norm of the projected gradient measures how far we are from satisfying a first-order optimality condition, namely how far the negative gradient is from being in the normal cone of f to the set X (Dang and Lan 2015, Proposition 4. For this condition, Algorithm Than the following guarantee: Theorem 3.1 (Dang and Lan (015 ). If f is -strongyysmoooe
=f(x!)) -mingxx x fu), and
Exll9((x, Ml I G 4 i [6] then SBMD needs O
[8F2
5 Σ i== G3) oracle calls to reach an
e-stationary-point X measured by 19
We next provide guarantee for ASCA in the form of reduction strongly-conver optimization algorithms. This is accomplished by the construction of the solving of a surrogate function at each iteration, which in the Euclidean case is effectively adding weight-decay. ASCA is useful in the case when efficient strongly-convex solvers are available for some or all of the blocks; for example, this is frequently the case for feature map selection problems such as our kernel approximation examples, which employ fz-regularized ERM in the inner optimization. Taking inspiration from Zhang and He 2018), for ASCA we analyze a stronger notion of stationarity that upper-bounds [=)x())] which term the projected stationarity measure: A (2:) (x]=| + ) D=(x=ll2) for x+ prox (Ir). Note that this is not the same measure used by Zhang and He (2018), although in the appendix we show that in the single-block case our result holds for their notion also.
Theorem 3.2. If f is B-strongly-smoode and F = f()(1) min f(u) then after T iterations ASCA yields a point x E X s.t. BlGg 48 (r)]l² - EA 48 (x) - 83b + +)), where E > 0 is the solver tolerance and the expectation over the randomness of the algorithm and associated oracles.
Proof Summary. The proof generalizes result of Agarwal et al. 2019) and is in Appendix A
Thus if we have solvers that return approximate optima of strongly-conver functions on each block then can converge to stationary point of the original function. The convergence rate will depend on the solver used; for concreteness we give a specification for stochastic mirror descent.
Corollary 3.1. Under the conditions of Theorem 3.1 if on i ASCA uses the Epoch-GD method of Hazan and Kale 2014) with divergence Dw; then O to reach an e-stationary-poine x E X as measured by Lipschitz constant of w; w.E.t. || lls-
9F6 b 1=1
C + ++ 12T2, oracle calls suffice
x
BlGg (x) where Lws, the
This oracle complexity matches that of Theorem 3.1 apart from the extra B term due to the surrogate function, which we show below is practice a minor term that does not obviate the benefit of aoometry-awarenes. On the other hand, ASCA is much more general, allowing for many different algorithms on individual blocks; for example, many popular neural optimizers such as Adam (Kingma and Ba 2015) have variants with strongly-convex guarantees (Wang et al. 2019).
The Benefit of Geometry-Aware Optimization: We conclude this section with a formalization of how convergence of gradient-based architecture-seat algorithms can benefit from this optimization strategy. Recalling from our example, we have the architecture parameter space X1 consisting of [E] simplices over ( variables equipped with the I-norm and the shared weight space X₂2 W equipped with the Euclidean norm. We suppose that the stochastic gradients along each block i have coordinates bounded a.s. by o; O. Then if we run SBMD using SGD (f2) to optimize the shared weights and exponentiated gradient (E1) to update the architecture parameters, Theorem 3.1
implies that we reach an E-stationary point in O oi
stochastic gradient computations. The main benefit here is that the first term in the numerator is not of which would be the case we used SGD; this improvement is critical as the noise of of the architecture gradient can be very high, especially a policy gradient is used to estimate probabilistic derivatives.
In the case of ASCA, we can get similar guarantees assuming the probabilities for each operation are lower-bounded by some small 8 0 and that the space of shared weights is bounded by B; then the guarantee will be as above except with an additional Olog 1 + 132) term (independent of 01. (2). While for both SBMD and ASCA the odd term from training the architecture remains, this will be incurred even in archttecch training using SGD. Furthermore, in the case of ASCA it may be improved using adaptive algorithms (Agarwal et al. 2019 Wang al. 2019).
5

---

Under review as a conference paper at ICLR 2020
4 GENERALIZATION PROPERTIES OF THE BILEVEL FORMULATION
In Section 2 we described the weight-sharing hypothesis class (C, W) as a set of functions non- disjointly partitioned by set of configurations C sharing weights in W and posed the ERM problem associated with selecting a hypothesis from H(C, W). However, as mentioned in Section [ the ob- jective solved in practice is bilevel problem where separate validation set is used for architecture parameter updates. Formally, the bilevel optimization problem considered is
min WE WCC
(v(()
S.L.
w E arg min w'EW
LT CT
(3)
where T, V.V C Z is pair of training/vallidaionn sets sampled i..d. from D, the upper objective Ev (1 1 E(a.)e E(hlo) (z). y) is the empirical risk over V, and Lr (w, c) is some objective induced by T. We intentionally differentiate the two losses since training is often regularized.
This setup is closely related to the well-studied problems of model selection and cross-valie moss-vaaliatton. However, a key difference is that the choice of configuration c E C does not necessarily provide any control over the complexity of the hypothesis space; for example, in NAS it is often unclear how the hypothesis space changes due to the change in one decision. By contrast, the theory of model selection is often directly concerned with control of model complexity. Indeed, in possibly the most common setting the hypothesis classes are nested according to some total order of increasing complexity, forming a structure (Vapnik] 1982 Kearns et al., 1997). This is for example the case in most norm- norm-based regularization schemes. Even in the non- non-nested case, there is often an explicit tradeoff between parsimony and accuracy (Vuong 1989).
With the configuration parameters in architecture search behaving more like regular model param- eters rather than as controls on the model complexity, it becomes reasonable to wonder why most NAS practitioners have used the bilevel formulation. Does the rraiiig-validation split exploit the partitioning of the hypothesis space (C, induced by the configurations C? To see when this might be true, we first note that a key aspect of the optima of the bilevel weight-sharing problem the restriction on the model weights that they must be in the set arg min Cr Cr(we)) of the inner objective Lr. As we will see, under certain assumptions this can reduce the complexity of the hypothesis space without harming performance.
First, for any sample T C Z let Ho(T) (h w E arg min (r }} be the version space (Kearns et al. 1997. Equation 6) induced by some configuration e and the objective function. Second, let N(F be the I -ooe-ring number of L balls required to construct an E-cover of F (Mohri et al. 2012 Equation 3.60). These two quantities let us define a complexity measure over the shared weight hypothesis space:
of set of functions F at scale E > 0, i.e. the
Definition 4.1. The version entropy of H W) at scale e > 0 induced by the objective Cr is A(H, e, T) = log N (Ueec H.)
The version entropy is a data-dependent quantification of how much the hypothesis class is restricted by the inner optimization. For finite C, a naive bound shows that A(H, e, T) is bounded by log |C|+ + max.ec log N (H,(T)))), so that the second term measures the worst-case complexity of the global minimizers of Lr- In the feature selection problem, LT is usually strongly-conve loss due to regularization and so all version spaces singleton sets, making the version entropy log C). In the other extreme case of nested model selection the version entropy reduces to the complexity of the version space of the largest model and so may not be informative. However, in practical problems such as NAS an inductive bias is often imposed via constraints on the number of input edges.
To bound the excess risk in terms of the version entropy, first discuss an important assumption that describes cases when we expect the shared weights approach to perform well:
Assumption 4.1. There exists good c* C, i.e. satisfying (w*,c' for some w²" E W. such that w.h.p. over the drawing of training set T ~ 'Dmr at least one of the minima of the optimization induced by e" and T has low excess risk, iee. w.p. 1 1-8 8 there exists w E arg min Cr(w', .c") s.t. Ep(hh ( Ep (c(( E for for excess risk E
arg minwxc ED
This assumption requires that w.h.p. the inner optimization objective does not exclude all low-risk classifiers for the optimal configuration. Note that it asks nothing in C, which may be arbitrarily bad, nor of the hypotheses found by the procedure. It does however
of either the other configurations

---

log N 8 Under review as a conference paper at ICLR 2020
prevent the case where one knows the optimal configuration but minimizing the provided objective Cr does not provide a set of good weights. Note that if the inner optimization is simply ERM over the training set T, i.. LT tr, then standard learning- theoorettt guarantees will give E 6) decreasing in mr and increasing most pol-logarithmicalyy in f. With this assumption, we can show the following guarantee on solutions to the bilevel optimization.
Theorem 4.1. Let be hypothesis corresponding to the solution of the bilevel optimization Then under Assumption 4.7 if l B-bounded we have w.p. 1 35 that
3B 2
(A(H,,,T)+ ! + +log !))
(h) S mmmn (h) + (mor 6) inf 3E esu
+
V
hElf
2
my
Proof Sketch. We decompose the excess risk (b()) - (. (h()))a
(h) - (h) (v(h) (v(s") + (v( ( ( lo (b
The first difference is bounded by the version entropy usng the constraint on h E H the second by optimality of h on V. the third by Hoeffding's s inequality, and the last by Assumption 4.1
As shown in the applications below, the significance of this theorem is that bound the ver- sion entropy guarantees excess risk almost as good as that of the (unknown) optimal configuration without assuming anything about the complexity or behavior of sub-optimal configurations.
Feature Map and Kernel Selection: In the feature map selection problem introduced in Section
C c= {dr: X + R" for i [k:]] a of feature maps and the inner problem LT is fg-regularized
ERM for linear classification over the resulting feature vectors. The bilevel problem is then
min <EC
by (v(h
S.t.
arg min w'ew
Alllol 112 +
Σ E((w', (x(2)).) (..8)ET
(4)
Due to strong-convexity of Lr, each map 6; induces a unique minimizing weight w E W and thus singleton version space, therefore upper bounding the version entropy by log CI log N. Further- more, for Lipschitz losses and appropriate choice of regularization coefficient, standard results for (z-regularized ERM for linear classification (e.g. Sridharan et al. (2008) show that Assumption
is satisfied with txe (mT, 8) O
+1 log }/
Then applying Theorem 4.1 yields
WeT
Corollary 4.1. For feature map selection the bilevel optimization
with X
log J/2 yields
(v
(h(h)= S minge[n) min ( (d)) +
11
log
In the special case of kernel selection using random Fourier approximation, we can apply associated generalization guarantees (Rudi and Rosasco 2017 Theorem 1) to show that we can compete with the optimal RKHS from among those associated with one of the configurations:
Corollary 4.2. In feature map selection suppose each map E C is associated with random Fourier feature approximation of continuous dhift-invarian kernel that approximates RKHS Ho and is the square loss. If the number of features d = ((ymm log mT// /5) and X = 1/ /mT
then w.p. 5 we have (h) S mingec minneH, (b) + O log
log
In both cases we are able to get risk bounds almost identical to the excess risk achievable we knew the optimal configuration beforehand, up to an additional capacity term depending weakly on the number of configurations. This would not be possible with solving the regular ERM objective in- stead of the bilevel optimization we would then have to contend with the possibly high complexity of the hypothesis space induced by the worst configuration.
Neural Architecture Search: In the case of NAS we do not have a bound on the version entropy, which now depends on all of C. Whether the version space, and thus the complexity, of deep net- gather some evidence.
works is small compared to the number of samples is unclear, although The question amounts to how many (functional) global optima are induced by a training set of size my. In an idealized spin-glass model, Choromanska et al. (2015) Theorem 11.1) suggest that the

---

Under review as a conference paper at ICLR 2020
Figure Validation accuracy on CIFAR-10 (left) and IMDB (right) of feature map selection with weight-sharing compared to full sweep of random configurations. Average over 16 seeds.
1.5
wacomss ve hakiing
randon Scarch
9/10
(2nden soarch
sUCeesiive hh ving
eaponentiated pradient
experentated prideet
percentie
0:53
92th percentre ef
8.52
velidzion
3:00
0.66
fealure dimensioo
number bins
rondnn search
Figure 2: Search time on CIFAR-10 (left) and IMDB (right) for feature map selec- tion. Weight-sharing finds configuration with almost the same validation accu- racy much faster than random search.
Ruzomsatve haiving
exporentionss gradient
1.a
exjicee ated grasient
2.8
3125
12500 33265
2430
10000
30000
12244
262144
164826
430054 5077223
feature dimerision
number of bins
number of critical points is exponential only in the number of layers, which would yield small version entropy. It is conceivable that the quantity may be further bounded by the complexity of so- lutions explored by the algorithm when optimizing Cr (Nagarajan and Kolter] 2017 Bartlett al. 2017]; indeed, we find that shared-wett weight optimization leads to models with smaller Eg --onrmm and distance from initialization than from-scracch SGD on single network (see Appendix DD4D. On the other hand, Nagarajan and Kolter (019)) argue, with evidence restricted settings, that even the most stringent implicit regularization cannot lead non-vacuous uniform convergence bound; if true more generally this would imply that the NAS version entropy is quite large.
5 EMPIRICAL RESULTS
Here we demonstrate how weight-sharing can be used as a tool to speed up general architecture search problems by applying it to feature map selection problems. We then validate our opti- mization analysis with geometry-aware weight-sharing method to design CNN cells for CIFAR-10.
Feature Map Selection: Recall that here configuration space has & feature maps Φ; X - R
with outputs passed to a linear classifier w E R", which will be the shared weights We will approximate the bilevel optimization (3) with the inner minimization over é2-regularized ERM
2|| + E(. ((w,, (z)), y). Our weight-sharing procedure starts with vector ((1) E AN encoding a probability distribution Pea: over [N] and proceeds as follows:
1. For each point (x, y) T pick Pote) and construct featurization fa = (s(x).
2. Compute shared weights (1()) = arg min wew A||wo| - + EEe {((w,,o),8))
3. Update (1*+1) according to (an estimate of) its validation loss E(eyev (((w())
(((w((),x(x)) de(x))) u).
Observe the equivalence to probabilistic NAS: at each step the classifier (shared parameter) is up- dated using random feature maps (architectures) on the training samples. The distribution over them is then updated using estimated validation performance. We consider two schemes for this update of (()): (1) exponentiated gradient using the score-functio coreeffuntion estimate and (2) successive elimination, where we remove a fraction of the feature maps that perform poorly on validation and reassign their probability among the remainder. (1) may be viewed as softer version of (2), with halving also having only one hyperparameter (elimination rate) and not two (learning rate, stopping criterion).
The first problem we consider is kernel ridge regression over random Fourier features (Rahimi and Recht 2008) on CIFAR-10. We consider three configuration decisions: data preprocessing. choice of kernel, and bandwidth parameter. This problem was considered by Li et al. (2018), except they fixed the Gaussian kernel whereas we also consider Laplacian; however, they also select the regu- larization parameter X, which weight-sharing does not handle. We also study logistic regression for
8

---

Under review as a conference paper at ICLR 2020
Test Error
Params
Search Cost Days)
Comparable Search Space?
Search
Architecture
Source
Average
(M)
Method
Shake-Shake
Devries and Taylor 2017
N/A
2.56
26.2
manual
PyramidNet
Tamanta
2.31
26
manual
NASNat-A"
Zoph cla
2018
N/A
2.65
5.3
2000
N
RI.
AmocbaNet-B"
Real sl
2018
NIA
2.55
= 0.05
2.8
3150
ovolution
Random search WS
1i
kalwalkrr
2019
2.71
2.85
0.08
3.8
0.7
Y
random
ProxylessNAS
C3 Rl 2019
2.08
N/A
5.7
4
N
gradient-based
ENAS
Pham 2013
2.89
NíA
4.6
0.5
Y
RI. gradient bused
ASNG-NAY NAS
Astmolo el al
2019
NIA
2.83
0.34
3.9
0.1
Y
SNAS
Xie
2119
NIA
2.85
0.02
2.8
1.5
Y
gradient-hased
DARTS (first order)
Liu ct gl
2019
N/A
3.00
+ 0.14
3.3
0.4
Y
gradient-based
DARTS (second onder)?
et 2019
2.76
0.09 N/A
3.3
gradient- hased
PDARTS
Chen of
2019
2.50
3,4
0.3
Y
gradient-based
XNAS
Ours
2.54
2.70
3.8
0.3
gradient hused
EDARTS
2.69 0.30
3.9
crudient-bases
Table I: CIFAR-10 Benchmark: Comparison with manual networks and SOTA NAS on final (Stage 3) results. The results are grouped by those for manually designed networks, full evaluation NAS, weight-sharing NAS, and methods that we evaluated. All test errors 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. and our results were procured using Tesla V100 GPUs. We show results for networks with comparable number of parameters. For fair comparison conducted in stage 1. We exclude the cost for stage and evaluation for the same reason. # We evaluate the reported architecture found by XNAS using the DARTS training scheme for fair comparison.
Note that search cost is hardware-dependee
other work, show the stage cost for single search trial instead of the four
IMDB sentiment analysis of Bag-of- oee-off----mmmm (BonG) featurizations, a standard NLP baseline (Wang and Manning, 2012). Here there are eight configuration decisions: tokenization method, whether to remove stopwords, whether to lowercase, choice of n, whether to binarize features, type of feature weighting, smoothing parameter, and post-processing. As some choices affect the feature dimension we hash the BonGs into a fixed number of bins [Weinberger et al. 2009).
To test the performance of weight-sharing for feature map selection, randomly sample 64 con- figurations each for CIFAR-IO and IMDB and examine whether the above schemes converge to the optimal choice. The main comparison method here is thus random search, which runs full sweep over these samples; by contrast successive halving will need to solve 6 = log, 64 regression prob- lems, while for exponentiated gradient perform early stopping after five iterations. Note that weight-sharing can do no belter than random search in terms of accuracy because they are picking configuration from a space that random search sweeps over. The goal is to see if it consistently returns a good configuration much faster. As our results in Figures [ and 2 show, successive halv- ing indeed does almost as well as random search in much less time. While exponentiated gradient usually does not recover a near-optimal solution, it does on average return a configuration in the top 10%. We also note the strong benefit of over-pate rre-parameterization for IMDB- the n- n-gram vocabulary has size 4 million so the number of bins on the right is much larger than needed to learn in a single- configuration setting. Overall, these experiments show that weight-sharing can also be used as a fast way to obtain signal in regular learning algorithm configuration and not just NAS.
NAS on CIFAR-10: Recall from Section 3hat when the architecture space consists of F.| simplices of dimension [O], the convergence rate of exponentiated gradient descent to a stationary point of the objective function is independent of the dimension of the space, while SGD has linear dependence. This result motivates our geometry -waare aware method called Exponentiated DAA--ARTTS RARTS (EDARTS).
EDARTS modifies first-order DARTS in two ways. First, in lieu of the softmax operation used by DARTS on the architecture weights, we use standard normalization so that the weight of operation
o on edge (i,j) is u. (1.)) = <("")/ /Eo eo' (t.5) Second, in lieu of Adam, we use exponentiated gradient to update the architecture weights: C₂- = c exp(-17Ve V.ly y (G-L). While EDARTS resembles XNAS (Nayman et al. 2019), our justification for using exponentiated gradient comes directly from aligning with the optimization geometry of ERM. Additionally, EDARTS only requires two straightforward modifications of first-order DARTS, while XNAS relies wipeout subroutine and granular gradient-clipping for each edge operation on the cell and data instance level.
'Our own XNAS implementation informed by correspondence with the authors did not produce competitive results. We still compare the architecture XNAS reported evaluated by the DARTS training routine in Table

---

Under review as a conference paper at ICLR 2020
We evaluate EDARTS on the task of designing CNN cell for CIFAR-I0. 10. We use the standard search space as introduced in DARTS (Liu et al. 2019) for evaluation we use the same three stage process used by DARTS and random search with weight-sharing (Li and Talwalkar 2019), with stage results considered the 'final' results. We provide additional experimental details in Appendix [
Table the performance of EDARTS relative both manually designed and NAS- MAS-discovered architectures. EDARTS finds an architecture that achieves competitive performance with manually designed architectures which have nearly an wnder-of-magnituue more parameters. Additionally, not only does EDARTS achieve significantly lower test error than first-order DARTS, it also outperforms second order DARTS while requiring less compute time, showcasing the benefit of geometry- aware optimization. Finally, EDARTS achieve comparable performance to the reported architecture for state-of-the-art method XNAS when evaluated using the stage training routine of DARTS.
Following XNAS (Nayman et al. 2019), we also perform an extended evaluation of the best ar- chitecture found by EDARTS with AutoAugment, cosine power annealing (Hundt al.) 2019). cross-entropy with label smoothing (Szegedy al. 22055), and trains for 1500 epochs. We evalu- ated the XNAS architecture using our implementation for a direct comparison and also to serve as reproducibility check. EDARTS achieved test error of 2. 1.18 in the extended evaluation compared to 2.15% for XNAS in our reproduced evaluation; note the published test error for XNAS is 1.81%.
To meet higher bar for reproducibility report 'broad reproducibility' results by repeating the entire pipeline from stage to stage 3 for two additional sets seeds. Our results in Table 2 (see Appendix) show that EDARTS has lower variance across experiments than random search with weight sharing (Li and Talwalkar 2019). However, we do observe non-negligible variance in the performance of the architecture found by different random seed initializations of the shared-weights network, necessitating running multiple searches before selecting an architecture.
REFERENCES
N. Agarwal, B. Bullins, X. Chen, E. Hazan, K. Singh, C. Zhang, and Y. Zhang. The case for full- matrix adaptive regularization. In Proceedings of the 36th International Conference Machine Learning. 2019.
Y. Akimoto, Shirakawa, N. Noshinari, K. Uchida, S. Saito, and Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In International Conference on Machine Learning, 2019.
S. Arora, Y. Liang, and T. Ma. A simple but tough-to-beat baseline for sentence embeddings. In Proceedings of the 5th International Conference on Learning Representations, 2017.
Bartlett, D. J. Foster, and M. Telgarsky. Spectrally normalized margin bounds for neural networks.
In Advances Neural Information Processing Systems, 2017.
A. Beck. First-Order Methods in Optimization. MOS-SIAM, 2017.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
L. M. Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7:200-217, 1967.
H. Cai, L. Zhu, and S. Han. ProxylessNAS: Direct neural architecture search target task and hardware. In International Conference on Learning Representations, 2019.
M. Carlucci, M. Esperança, M. Singh, V. Gabillon, Yang, H. Xu, Z. Chen, and J. Wang- MANAS: Multi-Agent Neural Architecture Search. arXiv e-prints, 2019.
X. Chen, L. Xie, J. Wu, and Q. Tian. Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation. arXiv e-prints, art. arXiv:1904.119 12760, Apr 2019.
A. Choromanska, M. Henaff, M. M. G. B. Arous, and Y. LeCun. The loss surface of multilayer networks. In Proceedings of the 18th International Conference on Artificial Intelligence and Statisties, 2015.
10

---

Under review as a conference paper at ICLR 2020
C. D. Dang and G. Lan. Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM Journal on Optimization, 25:856-8811 2015.
T. Devries and G. W. Taylor. Improved regularization of convolutional neural networks with cutout. 2017.
S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM Journal on Optimization, 23:2341 -2688, 2013.
E. Hazan and S. Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15:2489-2511 2014.
A. Hundt, V. Jain, and G. Hager. sharpdarts: Faster and more accurate differentiable architecture search. 2019.
K. Kandasamy, G. Dasarathy, J. Schneider, and B. Póczos. Multi-fidelity bayesian optimisation with continuous approximations. In International Conference on Machine Learning, 2017.
M. Kearns, Y. Mansour, A. Y. Ng. and D. Ron. An experimental and theoretical comparison of model selection methods. Machine Learning, 27:7-50, 1997.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
J. Lafferty, H. Liu, and L. Wasserman. Statistical machine learning. 2010.
K. A. Laube and A. Zell. Prune and Replace NAS. arXiv e-prints, art. arXiv:1906.07525 Jun 2019.
L. Li and A. Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, 2019.
L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar. Hyperband: A novel bandit- based approach hyperparameter optimization. Journal of Machine Learning Research, 18(185): 1-52, 2018.
jmlr wttpm//.o/ooppppee////////////// 5551 html
H. Liang, Zhang, J. Sun, X. He, W. Huang. K. Zhuang, and Li. DARTS+: Improved Dif- ferentiable Architecture Search with Early Stopping. arXiv e-prints, art. urXiv:1909.06033 Sep 2019.
H. Liu, K. Simonyan, and Y. Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
E. Loper and S. Bird. Nltk: the natural language toolkit. arXiv preprint cs/0205028, 2002.
I. Loshchilov and Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint 1PX1::1608.03883. 2016.
Mairal. Incremental majorization-miniiizzz minimizaiiinninn optimization with application large-scale ma- chine learning. SIAM Journal on Optimization, 25:829-855, 2015.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, 2012.
V. Nagarajan and J. Z.. Kolter. Generalization in deep networks: The role of distance from initializa- tion. arXiv, 2017.
V. Nagarajan and J. 7. Kolter. Uniform convergence may be unable to explain generalization in deep learning. In Advances in Neural Information Processing Systems, 2019. To Appear.
N. Nayman, A. Noy, T. Ridnik, I. Friedman, R. Jin, and I., Mennik-Mano.. Xnas: Neural architecture search with expert advice. 2019.
A. Noy. N. Nayman, T. Ridnik, N. Zamir, S. Doveh, I. Friedman, R. Giryes, and L. Zelnik-Mann Manno.. ASAP: Architecture Search, Anneal and Prune. arXiv e-prints, art. arXiv:1904.0411 Apr 2019.

---

Under review as a conference paper at ICLR 2020
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, et al. Scikit-learn Machine learning in python. Journal of machine learning research, 12(0ct):2825-2555) 2830, 2011.
H. Pham, M. Guan, B. Zoph. Q. Le, and Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning, 2018.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, 2008
M. Razaviyayn, M. Hong, and Z.-Q. Luo. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal Optimization, 23:1 126 1153, 2013.
E. Real, A. Aggarwal, Y. Huang, and Q. V. Le. Regularized Evolution for Image Classifier Archi- tecture Search. 2018.
A. Rudi and L. Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, 2017.
K. Sridharan, N. Srebro, and S. Shalev-Schwartz. Fast rates for regularized objectives. In Advances in Neural Information Processing Systems, 2008.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Ra- binovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1-9, 2015.
C. Szegedy, V. Vanhoucke, S. loffe, J. Shlens, and Z. Wojna. Rethinking the Inception Architecture for Computer Vision. arXiv e-prints, art. arXiv: 15 51..00567, Dec 2015.
K. Tsuda, G. Rätsch, and M. K. Warmuth. Matrix exponentiated gradient updates for on-line learn- ing and bregman projection. Journal of Machine Learning Research, 6:995-1018, 2005.
V. Vapnik. Estimation of Dependences Based on Empirical Data. Seringer-Verllage 1982.
Q H. Vuong. Likelihood ratio tests for model selection and non-nested hypotheses. Econometrica: Journal of the Econometric Society, pages 307-333, 1989.
G. Wang, S. Lu, W. Tu, and L. Zhang. Sadam: A variant of adam for strongly convex functions. arXiv, 2019.
S. Wang and C. D. Manning. Baselines and bigrams: Simple, good sentiment and topic classifica- tion. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguisties, 2012.
K. Weinberger. A. Dasgupta, J. Langford, A. Smola, and J. Attenberg Feature hashing for large scale multitask learning. In Proceedings of the 26th International Conference on Machine Learning. 2009.
S. Xie, H. Zheng, Liu, and L. Lin. SNAS: stochastic neural architecture search. In International Conference on Learning Representations, 2019.
Y. Yamada, M. Iwamura, and K. Kise. Shakedrop regularization. 2018.
Q. Yao, J. Xu, W.W. Tu, and Z. Zhu. Differentiable Neural Architecture Search via Proximal Iterations. arXiv e-prints, art. arXiv:1905.1 13577, May 2019.
Zhang and He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv, 2018.
B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le. Learning transferable architectures for scalable image recognition. In Conference on Computer Vision and Puttern Recognition, 2018.
12

---

Under review as a conference paper at ICLR 2020
A OPTIMIZATION
This section contains proofs and generalizations of the non-convex optimization results in Section
A.1 PRELIMINARIES
We first gather some necessary definitions and results from convex analysis. Definition A.1. Let X be a convex subset of fiiteeddimensionnl real vector space and X IR be everywhere sub cob--ffffrentable.
1. For 0, f a-strongly-conver w.E.. norm if z, X we have
[(v)
(VI(z), x) + 2 f1y - =1|
2. For 3 > 0, f is B-stronggy-smooot w.z.t norm ||. if x. E A' we have
f(0) S + (V/(),
Definition A.2. Let X be convex subset of a finite-dimensionall real vector space. The Bregman divergence induced by strictly convex cestance-generatiin function (DGF) w: R is
Du(zlly) w(x) w(y) (Vw(y), y) V,, y E X
By definition, the Bregman divergence satisfies the the following properties:
1. (u(xll)) 2 o X and (= = ==
2. If w is a-strongly-comee w.t. norm || then so is D-((lly) 4 E X. Furthermore, (x () e y/1² V v.y E X.
2
3. If w 3-strongly-smool w.r.f norm || then so Da(-lly) V E X. Furthermore, (1
([oll/) ()
| - u|ا² v x, y E X.
Lemma A.1 (Three-Points Lemma). Beck 2017
Lemma 9.11) For any DGF w : X ++ IR and all
F, y. 2 we have
(Vw(y) [w(x), x) = (=(ellæ) + Du(zily) (=lllly)
Definition A.3. Les X + be a I-strongly-comvex DGF. Then for constant and an everywhere sub-differee uub-differentiable function f X + IR the proximal operator is defined over E X as
prox, (x) = arg min (f - (ull(z)
wex
Note that the prox operator well-defined whenever will also use the following notation for the proximal gradient operator:
B-strongly-smoone for some < X. We
proxV x (z) arg aig ((V u) (ullz)
aex
Note that the prox grad operator is always well-defined.
Theorem A.1. (Beck 2017 Theorem 9.12) For any > I-strongly-convex DGF X + TR, R be everywhere sub-differentiable function s.A. Xf(-) (=(-1lz) is
and x X let f convex over X. Then for xt = proxx(0 (x) and u E X we have
X f:X
+
(Vw(x)- Vw(x ),u- u- x+) S -
Lemma A.2. For any X >> 0, I-strongly-conver DGF w X TR, and x E X let f + R be an everywhere sub-differentiable function Af(-) Dw (- (|x) is convex over X. Then
XJ(x) - f(x )) 2 (= ||x) + (=(ll==*
Proof. Applying Theorem A.I followed by Lemma
yields
Xf((x) f(x+)) 2 (Vw(x) Va(a++ ) x (u(al(=tt + (=( (xlla)))
Corollary A.1. For any X 0, I-strongly-comvex DGF X + R. x X. and everywhere
sub-differentiable funccttto f X + R. we have for x = V (x) that
(V)()), -
D=(x (=(l+
13

---

Under review as a conference paper at ICLR 2020
A.2 STATIONARITY MEASURES
Because we consider constrained non-convex optimization, we cannot measure convergence to sta- tionary point by the norm of the gradient. Instead, analyze the convergence proximal-mapping- based stationarity measures. The most well-known measure is the norm of the projected gradient (Ghadimi and Lan 2013), which in the unconstrained Euclidean case reduces to the norm the gra- dient and in the general case measure the distance between the current point and a cone satisfying first-order optimality conditions (Dang and Lan 2015| Proposition 4.1). Our convergence results hold for a stronger measure that we call the projected stationarity and which is inspired by the Breg- man stationarity measure of Zhang and He (2018) but using the prox grad operator instead of the operator.
Definition A.4. Let w X + R be I-strongly-comee DGF and f X + R be an everywhere sub sub-differentiabee function. Then for any we define the following two quantities:
1. The projected gradient of f at I E X (s 2 --
2. The projected stationarity of f X (x()) Du(ell (x))++ Durcot (x))la)))
The following properties follow:
1. x Rd for some 2 1 and w(.) = 1lll 11 then we have Gx(x) = vf(x).
2. [[ (x)
We can also consider the Bregman stationarity measure of Zhang and He (2018) directly. As this measure depends on the prox operator, which not always defined, we first state the notion of non-convexity that Zhang and He (2018) consider.
Definition A.S. An everywhere sub-differentiabt function ; + R is (7, w) -eeatiiely-weakly convex ((,,w)-RWe) for >> 0 and w + IR a I-strongly-convex DGF if f(.) + rw(+) is conver over X. Note that all yysttrongyy-smn
functions are (Y.W)-RWC.
Note that (7,w)) RWC is generalization of strongly-convex. Furthermore, for such functions we can always define the prox operator for y allowing us to also define the Bregman gradient below. Similarly to before, bounding the Bregman stationarity measure yields stronger notion of convergence than the squared norm of the Bregman gradient. For the relationship between the Bregman stationarity measure and first-order optimality conditions see Zhang and He (2018 Equation 2.11).
w.r.t the norm w.r.t. which w is
Definition A.6. Let X be I-strongly-comee DGF and f everywhere sub rub-differentiable function for some > 0. Then for any X > 7y we define the following two quantities:
R a (r,w)-RV RWC
1. The Bregman gradient of at x. E X is 2 (x)
2. The Bregman stationarity of at X' (x(s) (a (rrux prox, (x)) D., (pros, (x)]
X
Note that, similarly to Definition A.4
[x) VOEX.
14

---

Under review as a conference paper at ICLR 2020
A.3 SUCCESSIVE STOCHASTIC STRONGLY CONVEX APPROXIMATION FOR CONSTRAINED NON-CONVEX NON- NON-EUCLIDEAN OPTIMIZATION
Here we prove our main optimization results. We begin with descent lemma guaranteeing im- provement of a non-convex function due to approximately optimizing a strongly convex surrogate. Lemma A.3. Let X R. be l-strongly-convex DGF and f X + R be everywhere sub- differentiable. For some x E X and p > define fa()) = f() + (-1lx) and let E X be point s.t. (fz min fu( S E. Then
1. If f is B-strongly-smonn
> 3, and X =
- f(0)) +E. we have that [Tx S B(f(x) f(ø)) +
1 then 2p
2. If f is (7,
7, and X = 1 2p
Proof. Generalizing an argument in Agarwal et 2011 Theorem A.2), for x X' have by stroni-convexity of fa that
- -(()) 2 E((()) fa(t)) = [(x)) - min f(u) + min f(u) - f(0) uEX
dEd
2 f(x) - f(x+)=+++ -
= =xxx) - -(xx)) - pD (xt1))
If f is B-strongly-smoon set x+ proxV, (z), so that by Corollary A.1 we have
f(x) -xxx)=+++++++)))+=)){( - pD 1|x) 2 (VS(x), - x 2 || x+ $112 ppD +1xx)
(= + Du (x)l 1115- 1155-x111 x=11
pD (x (|x))
p) (Du( [|x) (z(lxr)))
2 π -P))
Axx))
In the other case of f being (7, () RWC set x+ = prox (2),, so that by Lemma A.2 we have
Du(x+ (x) + D (all(tt pDD
((x)=((x*) (1=(=*11=>))
A
2 (Dt((tllz)) + (=(xlx=t)
2 Tx(x)
We now turn to formalizing our multi-block setting and assumptions. Setting A.1. For i 1.....b let X, be convex subset of a real vector space with an associated DGF wi : X; + IR that I-strongly-comvex w.rll some norm |ll over X,. We have an everywhere sub-differentiable function f X + R over the product space X x"_ X.
Our main results will hold for the case when the following general assumption is satisfied. We will later show how this assumption can follow from strong smoothness or relative weak convexity and existing algorithmic results.
Assumption A.1. In Setting A.l for any given e > O and each E [b] there exists constant P; > and an algorithm A, X + X that takes point E X and returns a point & E X satisfying f- = x- and
(J(s, x-1) + DrDan, (dellae) S + min (u, + p. DrD (ullzs)) wEX,
where the subscript i selects block i, the subscript - selects all blocks other than block and E.A. denotes expectation w.r.t. the randomness of algorithm A; and any associated stochastic oracles.
15

---

Under review as a conference paper at ICLR 2020
Algorithm 2: Generic successive convex approximation algorithm for reaching a stationary
point of the non-convex function Setting/A.)
Input: Point (²()) E in the product space Setting A.1 Algorithms ; X + d.
for iteration E [T] do
sample çt ~ [
update (++1) f Ag, (x(11)
Output:
Unif (2
Our main result relies the following simple lemma guaranteeing non-convex convergence for generic measure satisfying guaranteed expected descent:
Lemma A.4. In Setting A.1 for some & > and each E [6] ler F (x) be any measure s.I. for
some X and some algorithm A X + X we have Ag (g()) Pxi I (J(x)) - [(A(()))) +
Then the output of Algorithm 2 sstiisiiss
E (
F 77
where F f(x(11)) arg min (x) and the expectation is taken over the sampling at each iteration, the sampling of the output, and the randomness of the algorithms and any associated stochastic oracles.
Proof. Define E, = ((E.. Ac.))=- and note that ((++1) Aç. (x(1). We then have -x(()))((x(+t)))) ((c(T+1)))
F = fxx(1) - arg min f(x) 2 RE, (f(x11) -
uEX
EE,
Σ (f(z(0)) - f(x((11)))
1=1
T
Ez,_ Bg, BAG, (f(x!1) (0000)))((((()) f(x((+1)))
T
Es Σ
EA, (f(o((()) f(x(1+1)))
[=1
iml
A (1)
E
Ex;
(z)(t)
2
[=1 i=1
which implies that
T
( F
E
(1)
(x)
Ez,
S 2b (z((t))
T +e)
A
1=1
In the single-block setting, Lemmas A.3 and A.4 directly imply the following guarantee:
Theorem A.2. In Setting A. and under Assumption let = 1 and p satisfy one of the following:
1. f X + is 3-strongly-smooth and 23.
2. : X is (7, () some DGF w X + R and 27.
Then Algorithm 2 returns point x E X' satisfying of the following (respectively. w.r.t. the above settings) for F f(x(1) mingex f()
1.
83
+
2.
RI x 87 +6)
Here the expectation is taken the randomness the algorithm and oracle.
16

---

Under review as a conference paper at ICLR 2020
We apply a known result for the strongly convex for non-convex stochastic mirror descent, up to an additional depending on w:
recover the rate of offzhang and He (2018)
Corollary A.2. In Setting A.7 for 1 and (r,ww) (i,ww)-RR RRCC f. suppose have access to f through stochastic gradient oracle g (v)(x) such that Blgg S G Let A X + X be an algorithm that for any x E X runs the Epoch-GD method of Hazan and Kale
2014 with total number of steps
N, initial epoch length Ti 4 and initial learning rate in
on f. f(-) 2-Dl(-l
Then with NT calls to the stochastic gradient oracle Algorithm
2
returns point E X satisfying
F 16(G² + 4 (2) ET E (x) 8y
7N
for = f(x()) - min (() and Lu the Lipschitz constant of w w.r.t. ||. over X. So an expected iatationary-poing as measured by E /TY, can be reached O ( (0/ 1 oracle calls.
(1F(G2
Proof. Apply Theorem 5 of Hazan and Kale 2014) together with the fact that fa is y-strongly- convex w.r.t. || and its stochastic gradient is bounded by G2 + 2
For the multi-block case our results hold only the projected stationarity measure:
Theorem A.3. In Setting A.1 and under Assumption A.7 assume f(., is B-strongly- smoohh w.E.t l|te) over X, for each E [b] and each x=; E X-s If = P) = ...
pb = 23 and F = f(x(1)) - minnex {u) then Algorithm returns a point x E X' satisfying
2
F
EA 48
(z)
5
+E
T
Here the expectation is taken over the randomness of the algorithm and oracle and the projected stationarity measure a is defined w.r.t. the Bregman divergence of the DGF
(i:):)
Proof. For each block i [b] the conditions of Lemma A.4 are satisfied by assumption and applying Lemma A.3 to the projected stationary measures
(x) Du, (zil (1) (x)) + Du, (proxV) (x)lz))
X
/ (x) arg min (z) u) Da, (u|lx;). To apply Lemma A.4 in the multi- where proxVy A block setting it suffices to show that the sum of the projected stationarity measures on each block is equal the projected stationarity measure induced by the sum of the DGFs. For some 0 and any E [b] we have that
Vrox (x()s
arg min (VV((x), Dw(ullz)) NEX
b
arg min A uE
Σ (Vif(z)) u1) + Dw, Du, (u.llx;)
arg min A(V ((V.f(x),))) u) + Dw, (ullzz) = prox (x) wEX,
and
Ax = (x prox V (x)) Dw V
X2
Da, (I; proxV (x)) + Dw, (
X
6
b
1
Da, (m: prox V (x)) Dw, (prox (x)]l())) ( Σ (0)
2
Thus applying Lemma
A.2
with
yields the result.
17

---

Under review as a conference paper at ICLR 2020
In the following corollary recover the rate of Dang and Lan (2015) for non-convex block- stochastic mirror descent, up to an additional term depending on wi
Corollary A.3. Setting A. for 3-strongly-smmooth [. suppose we have access to ttrooghh stochastic gradient oracle g(x) = EV f(x) such that Ellgsil(0,. S G.. For i [b] let A; X + X be algorithm that for any
X runs the Epoch-GD method of Hazan and Kale (2014) with total number of steps N, initial epoch length T1 = and initial learning rate in on surrogate
function f.(.)= f(: + 2. (-11x;). Then with NT calls to the stochastic gradient oracle Algorithm 2 returns point X satisfying
F
16
EA (x) 836
[
max G L2,
3N
KE(
for F f(x()) - m f() and L., the Lipschitz constant of wi w.r.t. || ll()) over X, So an expected --staionnry-poinn as measured by TR oracle calls bounded by
/AA+t to* can be reached in a number of stochastic
BFb Σ G. 2.+
We can specialize this to the architecture search setting where have configuration search space contained in the product of simplices induced by having n decisions with choices each together with parameter space bounded in Euclidean norm. Corollary A.4. Under the assumptions of Corollary two geometries:
suppose b = 2 and we have the following
X1 = X (p 16, 11 ||e|| = 1}, || (1a) 11.11, wi(+) = log(.))
X22 - (w ER:::: ||ll2 < B}, || (1(2) - 11 112. w2(+) 1
Suppose the stochastic gradient oracle of f has bounded -nomm d over X1 and 02 over X2. Then Algorithm[[wil return an expected E-stationary point of f under the projected stationarity measure in number of stochastic oracle calls bounded by
0 3Fb g4
1 + ozd 32 B²)
o + 3 log
8
18

---

Under review as a conference paper at ICLR 2020
B GENERALIZATION
This section contains proofs of the generalization results in Section 4
B.1 SETTINGS AND MAIN ASSUMPTION
We first describe the setting for which we prove our general result.
Setting B.1. Let be a set of possible architectureconfguuraiiosss of finite size such that each e. E is associated with a parameterized hypothesis class H.=(hy X + Y E W} for input space Z = X x Y and fixed set of possible weights W. We will measure the performance of a hypothesis fw 8: x + [-,, B).
input v) E Z using l c) E(hw (x), 3) for some B-bounded loss
We are given training sample T ~ Dmr of size and validation sample V ~ Dmv of size my, where D is some distribution over the input space Z. Abusing notation, we will denote the the population risk by (h( E c) BBwDE=( c) and for any finite subset S C Z we will denote the empirical risk by lg (hw Es(w,
ExEst
Finally, we will consider solutions of optimization problems that depend on the training data and architecture. Specifically, for any configuration E C and finite subset S Z let Wc(S) W be the set of global minima of some optimization problem induced by and e and let the associated
version space (Kearns et al. 1997) be Hc(S) = =(hee E Wc))).
We next give as examples two specific settings encompassed by Setting B.I
Setting B.2. For feature map selection, in Setting B.I the configuration space is a set of feature maps X Rdd the set of weights W C IRd consists of linear classifiers, for inputs X the hypotheses are ((()) (x) = (fe(s), w) for w E W, and so Wc(S) is the singleton set of solutions to the regularized ERM problem
arg min wEW
X||
+ Σ
(x.N)ES
for some coefficient > O.
Setting B.3. For neural architecture search, Setting B. the configuration space consists of all possible choices of edges on a DAG of N nodes and choice from one of K operations al each edge, for a total number of configurations bounded by KN The hypothesis (() X + is W and the loss
determined by choice of architecture E and set of network weights Y x + {0,1} is the zero-one loss. In the simplest case Wc(S) is the set of global minima of the ERM problem
Σ (x),))
min WEW
(F.8)SS
We now state the main assumption we require.
Assumption B.1. In Setting B. there exists a good architecture c² E C, i.e. one satisfying (w" ..) E arg minwxe lD c) for some weights w² E W. such that w.p. - over the drawing of training set ~ Din at least one of the minima of the optimization problem induced by c and T has low excess risk, i.e. 3 w W.r (T)) s.t.
(o(w,c²) to(w", (²)) Sc-(TTT
for some error function E
Clearly, we prefer error functions E., that are decreasing in the number of training samples mr and increasing at most goly-logarithmically in This assumption requires that we knew the optimal configuration priori, then the provided optimization problem will find good set of weights for it. We will show how, under reasonable assumptions, Assumption B.I can formally shown to hold
in Settings B.2 and B.3
19

---

Under review as a conference paper at ICLR 2020
B.2 MAIN RESULT
Our general result will be stated in terms of covering numbers of certain function classes
Definition B.1. Let H be class of functions from X to Y. For any & > the associated Loo covering number N (HH,)) of H is the minimal positive integer such that H can be covered by balls of L -radius E.
The following is then a standard result in statistical learning theory (see e.g. Theorem 7.82)):
Lafferty et (2010)
Theorem B.1. Let H. be a class of functions from to Y and let l Y x X + [0, B] be an L-Lipschitz, B-bounded loss function. Then for any distribution D over X Y have
me²
Pr Sw/Dm
sup (up ViEH
- es(h) 2 3E S 2N (H,E) exp
2B²
where we use the loss notation from Setting B.
Before stating our theorem, we define final quantity, which measures the log covering number of the version spaces induced by the optimization procedure over a given training set. Definition B.2. In Setting B.1 for any sample S C x define the version entropy to be A(H, e, S) = log N (Urec ())
Theorem B.2. In Setring B.1 ler (w, E W x C be obtained solution to the following opti-
mization problem:
arg (v(w,,) wEW,cEC
S.I.
Wc(T)
Then under Assumption B.J ( 8) S ED(w", (m'''w"))
we have w.p. that
+ Ext (mr: 8) + B
log +
1
inf e>0
35 + BV
2
(A(H,,,T) + log 7
2my
5
mv
Proof. We have that
( ( c²)
( - (v(
+ (v(ū,, - -v(ww,
lv(w,, c") (x(
+ (o(w, - -
each term of which can be bounded as follows:
1. Since i (T(T) for some E C the hypothesis space can be covered by the union of the coverings of (T'))) over E C, so by Theorem B.I we have that w.p. 1
2 my
(A(H,, log 1 })
( ev ( 2) inf 3e
B V
e50
2. By optimality of the pair (w, é) and the fact that w E We (T) we have
lv (v c²) & (v Ev (v é) = min (v( v min wE..))
wEW.
3. Hoeffding's inequality yields &y (w, -²) - (w, c²) S BBV 2my Logg w.p. -8
4. Assumption B.1 states that (wr, e²) luw", ,0("",e))) S Eo (m ( 8) w.p. 1 8.
20

---

Under review as a conference paper at ICLR 2020
B.3 APPLICATIONS
For the feature map selection problem, Assumption B. holds by standard results for fz-regularized ERM for linear classification (e.g. (Srihhaann al. (2008)) ):
Corollary B.1. Setting B.2 suppose the loss function & is Lipschitz. Then for regularization
parameter
log we have me
(1
||w013
1u2-1:11 mr
1
( (D(w", c*) cc) S0
log
We can then directly apply Theorem B.2 and the fact that the version entropy is bounded by log [C] because the minimizer over the training set always unique to get the following:
Corollary B.2. In Setting B.2 ler (ú, è) E W C be obtained as a solution to the following opti-
mization problem:
arg min (v(w, wEW
S.t.
w arg min
A|W +
Σ
((fe(x),w)..))
(x,0)ET
Then
(1
110111 ||00
|C|+1 5
( 2) (()
log
+
log
mr
8
my
In the special case of kernel selection we can apply generalization results for learning with random features to show that can compete with the optimal RKHS from among those associated with one of the configurations (Rudi and Rosasco 2017 Theorem 1):
Corollary B.3. In Setting B.2 suppose each configuration с E C. is associated with random Fourier feature approximation of continuous shift- hhift-invariat kernel that approximates an RKHS He- Suppose E is the squared loss so that (ú, ê) E W x C is obtained as solution to the following optimization problem:
arg min fv(w, cEC
s.l.
W arg min
A||WI1 +
Σ (Ue(z), w) - -y)²
wEW
(T.N)ET
the number of random features d ( log / and X 1/ /mT then w.p. - 8 have
(D()))) min min CEC kEH, (D(h) S O log /
+ 5
log
my
In the case neural architecture search we are often solving (unregularized) ERM in the inner optimization problem. In this case that the set empirical risk minimizers contains a solution that, rather than having low excess risk, simply has low generalization error; then applying Hoeflding's inequality yields the following: Corollary B.4. In Setting B.1 mization problem:
make assumption weaker than Assumption B. namely
let (vi, à)
E be obtained as a solution to the following opti-
w E arg min (r(w',e) mrg min (v(w,c) S.I. oEW
arg
w'EW
Suppose there exists c* E satisfying (w","' E arg min fww c) for some weights w" W such that w.p. 1- 6 over the drawing of training set T Dmir at least one of the minima of the optimization problem induced by c² and T has low generalization error, i.e. 3 arg www Ex (rw,,, ,c')
(D(w.c') --c-c)-- - (r(w", )) S EC- (mT,,) "e(lw"c')==
for some error function ecr, Then we have w.p. 1 - 48 that
8 ( 6) < (o(w", ce)) Ee (MT, 0) BV 2my
log
B
log g 2mrr
2
1 A(H,,, log
+ inf 32 + B
8)
my
21

---

Under review as a conference paper at ICLR 2020
C FEATURE MAP SELECTION DETAILS
Solvers for Ridge regression and logistic regression were from scikit-learn (Pedregosa et al. 2011 For CIFAR-10 we use the kernel configuration setting from Li al. (2018) but replacing the regu- larization parameter by the option to use the Laplace kernel instead of Gaussian. The regularization was fixed to À The split is 40K/10K/10K, For IMDB we consider the following configuration choices:
1. Tokenizer: removing punctuation, splitting on punetuation, custom NLTK (Loper and Bird 2002)
2. removing stopwords or not
3. lowercasing or not.
4. order: n = 1,2,3, 3, higher order includes all lower-order n-grams
5. binarizing features or not
6. feature weights: saive-Bayes (Wang and Manning 2012 or smoothed inverse frequency (Arora al. 2017)
7. smoothing parameter for this weighting
8. preprocessing: None, fg-normalization, averaging by number of tokens
The regularization was fixed to C' = 1. The split is 25K/12.5K/12.5K
random
random search
successive halving exponentiated gradient 90th percentile of rs
successive halving
exponentiated gradient
0.91
90th percentile of
test accuracy
accuracy
0.90
0.89
0.50
0.87
0.48
0.86
0.46
100000
0.85
4196306 18771216
feature dimenslon
number of bins
Figure 3: Validation accuracy CIFAR-10 (left) and IMDB (right) of feature map selection with weight-sharing compared to a full sweep of random configurations. Average over 16 seeds.
D NAS EXPERIMENT DETAILS
We provide additional details on CNN NAS benchmark on designing CNN cells for CIFAR-10 below.
D.I SEARCH SPACE
We consider the same search space DARTS (Liu et al.) 2019). which has become one of the
standard search spaces for CNN cell search (Nayman et al. 2019 Chen et al. [219 Xie et al. 2019;
Noy et al. 2019 Liang et al. 2019). Following DARTS and random search with weight-sharing (Li and Ta wa kar 2019). our evaluation of EDARTS consists of three stages:
Stage the search phase, we run EDARTS with four random seeds to reduce variance from different initialization of the weight- network.
Stage 2: We evaluate the best architecture identified by each search run by training from scratch.
Stage 3: We perform more thorough evaluation of the best architecture from stage 2 by training with ten different random seed initializations.
22

---

Under review as a conference paper at ICLR 2020
For stages 2 and 3, we train each architecture for 600 epochs with the same hyperparameter settings as DARTS.
For completeness, describe the convolutional neural network search space considered. The set of operations O considered at each node include: (1) 3 separable convolution, (2) 5 x separable convolution, (3) 3 dilated convolution, (4) 5 x dilated convolution, (5) max pooling, (6) average pooling, (7) identity.
We use the same search space 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 operations that half the length and width dimensions of the input. In the experiments, for both cell types, we set N = 6 with 2 input nodes and 4 intermediate nodes, after which the output of all intermediate nodes are concatenated to form the output of the cell.
D.2 STAGE 1: ARCHITECTURE SEARCH
We use EDARTS to train a smaller shared-weight network in the search phase with 8 layers and 24 initial channels instead of the 16 used by DARTS. Additionally, to more closely mirror the architec- ture used for evaluation in stage 2 and 3, we use auxiliary head with weight 0.4 and scheduled path dropout of 0.2. For the EDARTS architecture updates, we use learning rate of 0.2 for the normal cell and 0.6 for the reduction cell. All other hyperparameters are the same as DARTS: 50 training epochs, batch size of 64, gradient clipping of 5 for network weights, SGD with momentum set to 0.9 and learning rate annealed from 0.025 to 0.001 with cosine annealing (Loshchilov and Hutter 2016), and weight decay of 0.0003.
D.3 STAGE AND 3: ARCHITECTURE EVALUATION
We use the evaluation scheme DARTS when retraining architectures from scratch. The larger evaluation network has 20 layers and 36 initial channels and is trained for 600 epochs using SGD with momentum set to 0.9, batch size of 96, and learning rate of 0.025 annealed down to O; the gradient clipping scheduled drop path rate and weight decay are identical to the search phase. We also use an auxiliary head (Szegedy al. 2015) with weight of 0.4 and cutout (Devries and
Taylor 2017).
D.4 DOES WEIGHT-SHARING PERFORM IMPLICIT REGULARIZATION
Percentage Difference in from init B Between Fixed Architecture and Mixture
Percentage Difference in 12, 12_norm Between Fixed Archtrecture and Mixture
al Keightt
weigtt
205_cor cora.arrir wos.oorn/wskkltt Wskglts
175%
125%
35%
50%
13
Figure 4: Norm comparison between weight of the best EDARTS architecture trained from scratch versus that of the corresponding shared-weights network.
We investigate whether neight-sharing implicitly regularizes the hypothesis space by examining the l2 norms and distance from initialization of the shared-weight weights network relative that observed when training the best EDARTS architecture from scratch. We use the same network depth and hy- perparameters as those used for the weights network to train the fixed architecture. Figure 4 shows the percent difference in the norms between the fixed architecture and the shared-weights network pruned to just the operations kept for the fixed architecture. From the chart, we can see that both the &g distance from initialization and the l norm of the weights is smaller than that fixed network are higher than that of the weight network by over 40%, suggesting weight-sharing acts form of implicit regularization.
23

---

Under review as a conference paper at ICLR 2020
Set
Set 2
Set
2
Stage 3
2
3
Stage 3
2
3
Stage 3
2.79
2.91
2.99
2,88
2.79
3.55
3.20
3.05
2.65
2.69
2.74
2.96
2.63
2.61
2.71
Table 2: EDARTS stage 2 and 3 test error for 3 sets of random seeds. The bolded test error the best stage performance across the 3 sets of random seeds.
D.5 DISCUSSION OF REPRODUCIBILITY NAS
Our 'broad reproducibility' results in Table 2 show that EDARTS has lower variance across experi- ments than random search with weight sharing (Li and Talwalkar 2019). However, we do observe non-negligible variance in the performance of the architecture found by different random seed ini- tializations of the whighd-weights network, necessitating running multiple searches before selecting an architecture.
24


Reviews:
[{"review_id": "rJevgbYIFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 work proposes an algorithm for handling the weight-sharing neural architecture search problem. It also derives generalization bound for this problem.\n\nThe reviewer has several concerns:\n\n1) the SBMD and ASCA algorithms are existing generic algorithms. The analysis in this work also looks very generic. There is a sense of disconnection with the considered training problems. The reviewer would like to see more discussions on how to connect the algorithms with specific NAS problems. For example, what is the beta parameter when training a NAS problem?\n\n2) The convergence rate improvement brought by using mirror descent has been long known. It is not easy to see what is the contribution of this work.\n\n3) The generalization part seems to be meaningful. But it may be much stronger if the NAS problem can also have a theoretical bound. It is less appealing to only discuss cases with strongly convex objectives.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "B1lBMGw2KB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "I have not worked in the optimization filed and I am only gently followed the NAS field. I might under-valued the theoretical contribution.\n\nThis work provides  theoretical analysis for the NAS using weight sharing in two aspects: \n1) The authors give non-asymptotic stationary-point convergence guarantees (based on stochastic block mirror descent (SBMD) from Dang and Lan (2015)) for the empirical risk minimization (ERM) objective associated with weight-sharing. Based on this analysis, the authors proposed to use  exponentiated gradient to update architecture parameter, which enjoys faster convergence rate than the original results in Dang and Lan (2015). The author also provided an alternative to SBMD that uses alternating successive convex approximation (ASCA) which has similar convergence rate. \n2) The author provide generalization guarantees for this objective over structured hypothesis spaces associated with a finite set of architectures.\n\nMy biggest concern is the validity of the proposed exponentiated gradient update, at least empirically. We indeed observed slightly improvement in test error over DARTS on the CIFAR10 benchmark but how reproducible the results are? Can you compare at least on the other benchmark (PENN TREEBANK) used in Liu et al 2019? Also, comparing to first order DARTS, search cost is the same and this is hard to justify the better convergence rate for EDARTS. In addition, the results on feature map selection is not very encouraging as the gap to the successive halving is significant.\n\nThe author proposed ASCA, as an alternative method to SBMD. Why we need such alternative? What is the advantage of ASCA comparing to SBMD? When should I use ASCA and when SBMD? How do they empirically different? \n\nThen I feel some wording can be improved. For example, \"while requiring computation training …”,  “…which may be of independent interest”.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Since there were only two official reviews submitted, I reviewed the paper to form a third viewpoint.  I agree with reviewer 2 on the following points, which support rejection of the paper:
1) Only CIFAR is evaluated without Penn Treebank;
2) The "faster convergence" is not empirically justified by better final accuracy with same amount of search cost; and
3) The advantage of the proposed ACSA over SBMD is not clearly demonstrated in the paper.

The scores of the two official reviews are insufficient for acceptance, and an additional review did not overturn this view.
Decision: Reject