XNAS: Neural Architecture Search with Expert Advice

Introduction

In recent years tremendous efforts have been put into a manual design of high performance neural networks [larsson2016fractalnet, hu2018squeeze, szegedy2016rethinking_label_smooth, szegedy2015going]. An emerging alternative approach is replacing the manual design with automated Neural Architecture Search (NAS). NAS excels in finding architectures which yield state-of-the-art results. Earlier NAS works were based on reinforcement learning [zoph2016neural, NASNET], sequential optimization [PNAS], and evolutionary algorithms [Real18Regularized], and required immense computational resources, sometimes demanding years of GPU compute time in order to output an architecture. More recent NAS methods reduce the search time significantly, e.g. via weight-sharing [ENAS] or by a continuous relaxation of the space [liu2018darts], making the search affordable and applicable to real problems.

While current NAS methods provide encouraging results, they still suffer from several shortcomings. For example, a large number of hyper-parameters that are not easy to tune, hard pruning decisions that are performed sub-optimally at once at the end of the search, and a weak theoretical understanding. This cultivates skepticism and criticism of the utility of NAS in general. Some recent works even suggest that current search methods are only slightly better than random search and further imply that some selection methods are not well principled and are basically random [li2019random, sciuto2019evaluating].

To provide more principled methods, we view NAS as an online selection task, and rely on Prediction with Experts Advice (PEA) theory [cesa2006prediction] for the selection. Our key contribution is the introduction of XNAS (eXperts Neural Architecture Search), an optimization method (section 2.2) that is well suited for optimizing inner architecture weights over a differentiable architecture search space (section 2.1). We propose a setup in which the experts represent inner neural operations and connections, whose dominance is specified by architecture weights.

Our proposed method addresses the mentioned shortcomings of current NAS methods. For the mitigation of the hard pruning, we leverage the Exponentiated-Gradient (EG) algorithm [kivinen1997exponentiated], which favors sparse weight vectors to begin with, enhanced by a wipeout mechanism for dynamically pruning inferior experts during the search process. Additionally, the algorithm requires less hyper-parameters to be tuned (section 3.2.2), and the theory behind it further provides guidance for the choice of learning rates. Specifically, the algorithm avoids the decay of architecture weights [goodfellow2016deep], which is shown to promote selection of arbitrary architectures.

Additionally, XNAS features several desirable properties, such as achieving an optimal worst-case regret bound (section 3.1) and suggesting to assign different learning rates for different groups of experts. Considering an appropriate reward term, the algorithm is more robust to the initialization of the architecture weights and inherently enables the recovery of ’late bloomers’, i.e., experts which may become effective only after a warm-up period (section 3.2.1). The wipeout mechanism allows the recovery of experts with a chance of being selected at the end of the process.

We compare XNAS to previous methods and demonstrate its properties and effectiveness over statistical and deterministic setups, as well as over $7$ public datasets (section 4). It achieves state-of-the-art performance over $3$ datasets, and top-NAS over rest, with significant improvements. For example, XNAS reaches $1.60\%$ error over CIFAR-10, more than $20\%$ improvement over existing NAS methods.

Proposed Approach

To lay out our approach we first reformulate the differentiable architecture search space of DARTS [liu2018darts] in a way that enables direct optimization over the architecture weights. We then propose a novel optimizer that views NAS as an online selection task, and relies on PEA theory for the selection.

We start with a brief review of the PEA settings and then describe our view of the search space as separable PEA sub-spaces. This enables us to leverage PEA theory for NAS.

The Search Space Viewed as Separable PEA Sub-spaces. We view the search space suggested by DARTS [liu2018darts] as multiple separable sub-spaces of experts, as illustrated in Figure 1, described next. An architecture is built from replications of normal and reduction cells represented as a directed acyclic graph. Every node $x^{(j)}$ in the graph represents a feature map and each directed edge $(j,k)$ is associated with a forecaster, that predicts a feature map $p^{(j,k)}:=p^{(j,k)}(x^{(j)})$ given the input $x^{(j)}$. Intermediate nodes are computed based on all of their predecessors: $x^{(k)}=\Sigma_{j<k}p^{(j,k)}$. The output of the cell is obtained by applying a reduction operation (e.g. concatenation) to the intermediate nodes. During the search stage, every forecaster combines $N$ experts’ feature map predictions $\{f_{i}^{(j,k)}\}_{i=1}^{N}:=\{f_{i}^{(j,k)}(x^{(j)})\}_{i=1}^{N}$ forming its own prediction,

Our architecture search approach is composed of two stages. In the search stage, the weights $w_{t,i}$ and $v_{t,i}$ are alternately optimized as described in section 2.2; then, in the discretization stage, a discrete child architecture is obtained as explained next.

The Discretization Stage. Once the architecture weights are optimized, the final discrete neural architecture is obtained by performing the following discretization stage, adopted from [liu2018darts]: Firstly, the strongest two predecessor edges are retained for each intermediate node. The strength of an edge is defined as $\max_{i}{u_{i}^{(k,j)}}$. Lastly, every forecaster is replaced by the corresponding strongest expert.

2 XNAS: eXperts Neural Architecture Search

The differential space, described in section 2.1, enables direct optimization over the architecture weights via gradient-descent based techniques. Previous methods adopted generic optimizers commonly used for training the network weights. For example [liu2018darts, xie2018snas, chen2019progressive, casale2019probabilistic] used adam [kingma2014adam], and [noy2019asap] used SGD with momentum. While those optimizers excel in joint minimization of neural network losses when applied to network weights, NAS is a essentially a selection task, aiming to select a subset of experts out of a superset. The experts weights form a convex combination, as they compete over a forecaster’s attention.

We argue that a generic alternate optimization of network weights and architecture weights, as suggested in previous works, e.g. [hundt2019sharpdarts, liu2018darts], is not suitable for the unique structure of the architecture space. Hence, we design a tailor-made optimizer for this task, inspired by PEA theory. In order to evaluate experts’ performance, a loss is to be associated with each expert. However, an explicit loss is not assigned to each expert, as opposed to a back-propagated loss gradient. Therefore, we base our algorithm on a version of the Exponentiated-Gradient (EG) algorithm adapted for the NAS space. EG algorithms favor sparse weight vectors [kivinen1997exponentiated], thus fit well to online selection problems.

The purpose of the wipeout step is threefold. First, the removal of weak experts consistently smooths the process towards selecting a final architecture at the descretization stage described in section 2.1. Thus it mitigates the harsh final pruning of previous methods, which results in a relaxation bias addressed in [snas, noy2019asap]. Second, it dynamically reduces the number of network weights, thus simplifying the optimization problem, avoiding over-fitting and allowing it to converge to a better solution. Last, it speeds-up the architecture search, as the number of graph computations decreases with the removal of experts.

Analysis and Discussion

In this section we analyse the performance of the proposed algorithm. For this purpose, we introduce the regret as a performance measure for NAS algorithms. Showing that the wipeout mechanism cannot eliminate the best expert (lemma 1), we provide theoretical guarantees for XNAS with respect to that measure (theorem 1). Proofs appear in Section LABEL:subsec:proofs of the supplementary material for brevity. Relaying on the theoretical analysis, we extract practical instructions with regard to the choice of multiple learning rates. Finally we briefly discuss the equivalence of our reward to the one considered by the policy gradient approach applied to NAS.

The Regret as a Performance Measure. Denote the regret, the cumulative losses of the forecaster and of the $i$th expert at time $t$ by,

respectively. The regret measures how much the forecaster regrets not following the advice of the best expert in hindsight. This criterion suits our setup as we optimize a mixture of experts and select the best one by the end of the process.

In classical learning theory, statistical properties of the underlying process may be estimated on the basis of stationarity assumptions over the sequence of past observations. Thus effective prediction rules can be derived from these estimates [cesa2006prediction]. However, NAS methods that alternately learn the architecture weights and train the network weights are highly non-stationary. In PEA theory, no statistical assumptions are made, as “simplicity is a merit” [hazan2016introduction], and worst-case bounds are derived for the forecaster’s performance. We obtain such bounds for the wipeout mechanism and the regret.

A Safe Wipeout. In XNAS (line 11), by the choice of the wipeout thresholds, experts with no chance of taking the lead by the end of the search are wiped out along the process. In a worse-case setup, a single incorrect wipeout might result in a large regret, i.e., linear in the number of steps $T$, due to a loss gap at each consecutive step. The following lemma assures that this cannot happen,

In XNAS, the optimal expert in hindsight cannot be wiped out.

The wipeout effectively transfers the attention to leading experts. Define the wipeout factor and the aggregated wipeout factor as $\Gamma_{t}:=1+\frac{\sum_{i\in I_{t-1}\setminus I_{t}}v_{t,i}}{\sum_{i\in I_{t}}v_{t,i}}$ and $\gamma_{T}:=\prod_{t=1}^{T}\Gamma_{t}$, respectively.

The aggregated wipeout factor satisfies $1\leq\gamma_{T}<N$.

Equipped with both lemmas, we show that the wipeout may improve the EG regret bound for certain reward sequences.

Regret Bounds. Our main theorem guarantees an upper bound for the regret,

The regret of the XNAS algorithm 1, with $N$ experts and learning rate $\eta$, incurring a sequence of $T$ non-negative convex losses of $\mathcal{L}$-bounded rewards, satisfies,

As an input parameter of XNAS, the learning rate $\eta$ cannot be determined based on the value of $\gamma_{T}$, since the later depends on the data sequence. Choosing the minimizer $\eta^{*}$ of the first two terms of (3) fully known in advance, yields the following tight upper bound,

The regret upper bound of XNAS is tight, as the lower bound can be shown to be of $\Omega(\mathcal{L}\sqrt{T\ln{N}})$ [haussler1995tight]. In addition, the wipeout related term reduces the regret in an amount which depends on the data sequences through $\gamma_{T}$, as it effectively contributes the attention of weak experts to the leading ones. For comparison, under the same assumptions, the worst-case regret bound of gradient-descent is of $O(\mathcal{L}\sqrt{TN})$ [hazan2016introduction], while the one of Adam is linear in $T$ [reddi2019convergence]. An illustration of the relationship between the regret and the rate of correct expert selection appears in section 8.3 of the supplementary material, where XNAS is shown to achieve a better regret compared to a generic optimizer.

Multiple Learning Rates. Equation 4 connects the optimal theoretical learning rate $\eta^{*}$ with the number of steps $T$, which is also the number of gradient feedbacks received by the experts. Since forecasters weights are being replicated among different cells, the number of feedbacks is different for normal and reduction cells (section 2.1). Explicitly, $T_{c}=d\times\mathcal{E}\times r_{c}$, where $T_{c},d,\mathcal{E},r_{c}$ are the effective horizon $T$, the validation set size, the number of epochs and the number of replications for cell type $c$ respectively. We adopt the usage of multiple learning rates $\eta^{*}_{c}$ in our experiments as upper bounds on the learning rates for minimizing the upper bound of the regret.

2 Key Properties and Discussion

In this section we discuss some of the key properties of XNAS. For each of this properties we provide supporting derivations, illustrations and demonstrations appearing in section 8 of the supplementary material for brevity.

We inspect the update term of GD with softmax,

Hence, the effective reward in this case is,

See derivations in section 8.4. The linear dependence on the expert’s weight $u_{t-1,i}$ in (6) implies that GD with softmax makes it harder for an expert whose weight is weak at some point to recover and become dominant later on, as the associated rewards are attenuated by the weak expert’s weight.

XNAS mitigates this undesirable behavior. Since for XNAS the update term (8) depends on the architecture weights only indirectly, i.e. through the prediction, the recovery of late bloomers is not discouraged, as demonstrated in section 8.1 of the supplementary material. From the very same reasons, XNAS is more robust to the initialization scheme compared to GD with softmax and its variants, as demonstrated in section 8.2 of the supplementary material. These advantages make XNAS more suitable for the NAS setup.

Note that while the XNAS enables the recovery of experts with badly initialized weights or with delayed rewards, the wipeout mechanism prevents inferior operations that start blooming too late from interfering, by eliminating experts with no chance of leading at the end.

Wipeout Factor. As mentioned in section 2.2, the wipeout mechanism contributes to both optimization process and search duration. A further reduction in duration can be achieved when the wipe-out threshold in line 11 of Algorithm 1 is relaxed with a parameter $0<\zeta\leq 1$, being replaced by $\theta_{t}\leftarrow\max_{i\in I_{t-1}}\{v_{t,i}\}\cdot\exp{\{{-2\eta\mathcal{L}(T-t)\cdot\zeta\}}}$. This will lead to a faster convergence to a single architecture, with the price of a violation of the theoretical regret. As worst-case bounds tend to be over pessimistic, optimizing over $\zeta$ could lead to improved results. We leave that for future work.

2.2 Fewer Hyper Parameters

The view of the differentiable NAS problem as an optimization problem solved by variants of GD, e.g. Adam, introduces some common techniques for such schemes along with their corresponding hyper-parameters. Tuning these complicates the search process - the fewer hyper-parameters the better. We next discuss how XNAS simplifies and reduces the number of hyper-parameters.

Theoretically Derived Learning Rates. The determination of the learning rate has a significant impact on the convergence of optimization algorithms. Various scheduling schemes come up, e.g. [loshchilov2016sgdr, smith2017cyclical], as the later additionally suggests a way for obtaining an empirical upper bound on the learning rate. In section 3.1, multiple learning rates $\eta^{*}_{c}$ are suggested for minimizing the regret bound (4), as $c\in\{N,R\}$ represents normal and reduction cells respectively. For example, for CIFAR10 with 50%:50% train-validation split, 50 search epochs, gradient clipping of $1$, $6$ normal cells and $2$ reduction cells both of $8$ experts for each forecaster, (4) yields $\eta^{*}_{N}=$7.5e-4 and $\eta^{*}_{R}=$1.3e-3.

Note that the proposed learning rates minimize an upper bound of the regret (4) in the case of no wipeout, i.e. the worst case, as the extent of the wipeout cannot be known in advance. Hence the proposed learning rate provides an upper bound on the optimal learning rates and can be further fine-tuned.

No Weight Decay. Another common technique involving hyper-parameters is weight decay, which has no place in the theory behind XNAS. We claim that the obviation of weight decay by XNAS makes sense. Regularization techniques, such as weight decay, reduce over-fitting of over-parametrized models when applied to these parameters [goodfellow2016deep]. No such effect is incurred when applying weight decay on the architecture parameters as they do not play the same role as the trained network parameters ${\boldsymbol{w}}$. Instead, weight decay encourages uniform dense solutions, as demonstrated in Figure 3.2.2, where the mean normalized entropy increases with the weight decay coefficient. The calculation of the mean normalized entropy is detailed in section 8.5 of the supplementary material. This observation could be associated with the suggestion of recent works [li2019random, sciuto2019evaluating] that current search methods are only slightly better than random search. The density of results in a harder degradation in performance once discretization stage occurs (section 2.1), hence sparse solutions are much preferred over dense ones.

No Momentum. The theory behind XNAS obviates momentum [qian1999momentum] and ADAM’s exponentially decay rates [kingma2014adam]. Since momentum requires more state variables and more computations, the resulting XNAS optimizer turns out to be simpler, faster and with a smaller memory footprint, compared to commonly used optimizers for NAS, e.g. ADAM [liu2018darts, xie2018snas, chen2019progressive, casale2019probabilistic] and SGD with momentum [noy2019asap].

Experiments and Results

In this section we will test XNAS on common image classification benchmarks, and show its effectiveness compared to the other state-of-the-art models.

We used the CIFAR-10 dataset for the main search and evaluation phase. In addition, using the cell found on CIFAR-10 we did transferability experiments on the well-known benchmarks ImageNet, CIFAR-100, SVHN, Fashion-MNIST, Freiburg and CINIC10.

Using XNAS, we searched on CIFAR-10 in a small parent network for convolutional cells. Then we built a larger network by stacking the learned cells, trained it on CIFAR-10 and compared the results against other NAS methods.

We created the parent network by stacking $8$ cells with $4$ ordered nodes, each of which connected via forecasters to all previous nodes in the cell and also to the two previous cells outputs. Each forecaster contains seven operations: 3x3 and 5x5 separable and dilated separable convolutions, 3x3 max-pooling, 3x3 average-pooling and an identity. A cells output is a concatenation of the outputs of the four cells nodes.

The search phase lasts $50$ epochs. We use the first-order approximation [liu2018darts], relating to ${\boldsymbol{v}}$ and ${\boldsymbol{\omega}}$ as independent parameters which can be optimized separately. The train set is divided into two parts of equal sizes: one is used for training the operations weights ${\boldsymbol{\omega}}$ and the other for training the architecture weights ${\boldsymbol{v}}$. With a batch size of $96$, one epoch takes $8.5$ minutes in average on a single GPUExperiments were performed using a NVIDIA GTX 1080Ti GPU., summing up to $7$ hours in total for a single search. Figure 9 shows our learned normal and reduction cells, respectively.

2 CIFAR-10 Evaluation Results

Where we used lemma 1 in (23), assuring that loss minimizer is among the remaining experts. Let us derive an upper bound:

Where (24) is due to (LABEL:eq:subset) and (25) is by setting,

Setting $\gamma_{T}:=\prod_{t=1}^{T}\Gamma_{t}$ with bounds specified in by lemma 2, we have,

Combining the lower and upper bounds and dividing by $\eta$,

We now bound the accumulated regret, using the convexity of the loss,

Supporting Materials for the Key Properties Discussion

In an attempt to demonstrate the possible recovery of late bloomers, we view an optimization problem in a three dimensional space as a prediction-with-experts problem, where each axis represents an expert with a constant prediction, i.e. $f_{t,x}\equiv(1,0,0),f_{t,y}\equiv(0,1,0),f_{t,z}\equiv(0,0,1)$ for the $x,y,z$ axes respectively. The forecaster then makes a prediction according to the following,

as the corresponding terms for the $x$ and $y$ axes are similar by symmetry, see a full derivation in section 8.4.2.

At the first stage the $z$ axis suffers many penalties as its weight shrinks. Then it starts receiving rewards. For GD with softmax, those rewards are attenuated, as explained in section 3.2.1 and can be seen in Figure 3 (right). Despite the linear loss, with constant gradients, the update term decays. Note that this effect is even more severe when dealing with more common losses of higher curvature, where the gradients decay near the local minimum and then further attenuated, as illustrated in section 8.2.4. Once the gradient shifts, it is already depressed due to past penalties, hence the $z$ axis struggles to recover. XNAS, however, is agnostic to the order of the loss values in time. Once the rewards balance out the penalties, the path leads towards the $z$ axis. In the meanwhile, the $y$ axis takes the lead.

2 A Deterministic 2D Axes Toy Problem

In section 8.1 we show the built-in attenuation of weak operations by GD with softmax. This is illustrated by a three dimensional toy example where the axes represent experts of constant predictions. Here we elaborate on this effect using a similar two dimensional toy problem, where the gradients with respect to the axes are the negative values of one another. See section 8.4.3 for the setup and full derivations. All the experiments in this section are conducted using a learning rate of $0.1$ for both optimizers for $50$ steps.

𝑥𝑦1x+y=1, and the trajectories are the solid lines with circles at their ends. Figure 4 illustrates the attenuation of gradients for GD with softmax, as although the gradients of the loss are constant, the gradients’ magnitude decreases as we move away from the initialization $\alpha_{x}=\alpha_{y}$, i.e. $(x,y)=(0.5,0.5)$. XNAS indeed receives constant gradients thus reaches the minima faster.

2.2 Imbalanced Initialization

The attenuated gradients also make GD with softmax more sensitive to the initialization, as demonstrated in Figure 5, where $\alpha_{x}=0<5=\alpha_{y}$ and GD with softmax, whose gradients are attenuated, makes no progress while XNAS reaches the minima.

2.3 The Preference of Dense Solutions

Presenting the attenuation factor $x\cdot y$ on the simplex, i.e. $x\cdot(1-x)$, in Figure 6, demonstrates how gradients are harder attenuated as far away as the variables move from a dense solution, e.g. $(x,y)=(0.5,0.5)$ at $\alpha_{x}=\alpha_{y}$.

Hence, it is harder for GD with softmax to strengthen a single expert over the other. This effect encourages dense solutions over sparse solutions, i.e. a choice of a single expert. Due to the descretization stage, described in section 2.1, the denser the solution is, the more degradation in performance is incurred. Hence dense solutions should be discouraged rather than encouraged.

2.4 Loss Functions of a Higher Curvature

3 Regret and Correct Selection in Statistical Setting

We consider a statistical setup for comparing XNAS with the common Gradient Descent (GD) with softmax, described in section 3.2.1. This setup simulates the iterative architecture optimization and final selection of the top expert for a single forecaster.

Two forecasters are compared, XNAS and GD with softmax. Both receive noisy independent and identically distributed (i.i.d) rewards of $N$ experts. Each expert has an initial i.i.d bias $\left\{b_{i}\right\}_{i=1}^{N}\sim\textrm{N}(0,1)$ simulating its inherent value, so its rewards satisfy $R_{t,i}\sim\textrm{N}(b_{i},\sigma_{R}^{2})$ for $i=1,\dots,N$ and $t=1,\dots,T$, where $\textrm{N}(\mu,\sigma^{2})$ is a Gaussian distribution with a mean $\mu$ and a standard deviation $\sigma$.

The first forecaster updates its weights using GD with softmax update rule from Equation 6 (full derivation in section 8.4.1), common to previous NAS methods, while the second is using Algorithm 1.

The forecasters use their update rules to update weights along the run. At the end of the run each selects the expert with the largest weight. A correct classification satisfies $\max\limits_{i=1,\dots,N}{\alpha_{i}}=\max\limits_{i=1,\dots,N}{b_{i}}$. The average regret of those runs is also calculated based on equation 2.

Figure 8 shows a mean of $1000$ Monte-Carlo runs, each of $1000$ time-steps, plotting the regret and the fraction of correct selection (classification). In Figure 8 (left), both terms are plotted versus a varying number of experts. It can be seen that the regret of XNAS is significantly smaller, scaling with the number of experts like $O(\sqrt{\ln{N}})$, as implied by its regret upper bound in equation 4, while GD regret scales like $O(\sqrt{N})$ [hazan2016introduction].

In Figure 8 (right), the noise standard deviation $\sigma_{R}$ is varying, making it harder to correctly classify the expert with the highest bias. Again, XNAS dominates GD with softmax, which is more sensitive to the noisy rewards due to the ’late bloomers’ described in 3.2.1, e.g. the best experts might suffer some large penalties right at the beginning due to the noise, thus might not recover for GD with softmax. In both graphs it can be seen that the correct selection fraction is monotonically decreasing as the regret is increasing. This gives an additional motivation for the use of the regret minimization approach as a criterion for neural architecture search.

4 Gradients Derivations

For the comparison to previous work [liu2018darts], we consider the decision variables $\alpha_{t,i}=\ln{v_{t,i}}$, as the right hand side is defined at (1).

where $\delta_{i,j}=\begin{cases}1,&\text{if }i=j,\\ 0,&\text{if }i\neq j.\end{cases}$ is the Kronecker delta.

4.2 The Derivation of Derivatives for the 3D Axes Problem

In this section we derive the derivatives with respect to the $x,y,z$ axes for the toy problem introduced at section 8.1. In this case,

Then, setting (38) and (40) in (37), we have,

where (41) is since $(x,y,z)\in\Delta$, defined in section 8.1. By symmetry we have,

The update terms for XNAS are according to (35),

4.3 The Derivation of Derivatives for a 2D Axes Problem

In this section we derive the derivatives with respect to the $x,y$ axes for a two dimensional toy problem. Similar to section 8.1 where a three dimensional problem was considered, now we consider only two axes. Each axis represents an expert of a constant prediction,

Then, setting (48) and (50) in (37), we have,

where (51) is since $x_{t}+y_{t}\equiv 1$. By symmetry we have,

5 The Mean Normalized Entropy

In this section we provide the technical calculation details of the mean normalized entropy, referred to in section 3.2.2. The normalized entropy of forcaster $(i,j)$ is calculated at the end of the search as following,

The mean is taken over all the forecasters in a normal cell, i.e.

where $\mathcal{I}$ and $\mathcal{J}$ are the sets of indices $i$ and $j$ respectively.

Detailed Experiments Setting

In this section we will describe the additional datasets that were used for transferability tests in section 4.3

CINIC-10: [darlow2018cinic] is an extension of CIFAR-$10$ by ImageNet images, down-sampled to match the image size of CIFAR-$10$. It has $270,000$ images of $10$ classes, i.e. it has larger train and test sets than those of CIFAR-$10$.

CIFAR-100: [cifar100] A natural image classification dataset, containing $100$ classes with $600$ images per class. The image size is $32$x$32$ and the train-test split is $50,000$:$10,000$ images respectively.

FREIBURG: [Freiburg] A groceries classification dataset consisting of $5000$ images of size $256$x$256$, divided into $25$ categories. It has imbalanced class sizes ranging from $97$ to $370$ images per class. Images were taken in various aspect ratios and padded to squares.

SVHN: [SVHN] A dataset containing real-world images of digits and numbers in natural scenes. It consists of $600,000$ images of size $32$x$32$, divided into $10$ classes. The dataset can be thought of as a real-world alternative to MNIST, with an order of magnitude more images and significantly harder real-world scenarios.

FMNIST: [fashionMnist] A clothes classification dataset with a $60,000$:$10,000$ train-test split. Each example is a grayscale image of size $28$x$28$, associated with a label from $10$ classes of clothes. It is intended to serve as a direct drop-in replacement for the original MNIST dataset as a benchmark for machine learning algorithms.

2 CIFAR-10 XNAS Search details

Data pre-processing. We apply the following:

Centrally padding the training images to a size of $40$x$40$.

Randomly cropping back to the size of $32$x$32$.

Randomly flipping the training images horizontally.

Standardizing the train and validation sets to be of a zero-mean and a unit variance.

Operations and cells. We select from the operations mentioned in 4.1, used with stride $1$ on normal cells, and with stride $2$ on reduction cells in edges connected to the two previous cells. Other edges in reduction cells are used with stride $1$. Convolutional layers are padded so that the spatial resolution is kept. The operations are applied in the order of ReLU-Conv-BN. Following [noy2019asap],[Real18Regularized], depthwise separable convolutions are always applied twice. The cell’s output is a $1$x$1$ convolutional layer applied on all of the cells’ four intermediate nodes’ outputs concatenated, such that the number of channels is preserved. In CIFAR-$10$, the search lasts up to $0.3$ days on NVIDIA GTX 1080Ti GPU.

3 Train Details

CIFAR-10. The training architecture consists of stacking up $20$ cells: $18$ normal cells and $2$ reduction cells, located at the $1/3$ and $2/3$ of the total network depth respectively. For the three architectures XNAS-Small, XNAS-Medium and XNAS-Large, the normal cells start with $36$, $44$ and $50$ channels respectively, where we double the number of channels after each reduction cell. We trained the network for $1500$ epochs using a batch size of $96$ and SGD optimizer with nesterov-momentum of $0.9$. Our learning rate regime was composed of $5$ cycles of power cosine annealing learning rate [hundt2019sharpdarts], with amplitude decay factor of $0.5$ per cycle and initial value of $0.025$. For regularization we used cutout [devries2017improved] with a length of $16$, scheduled drop-path [larsson2016fractalnet] of $0.2$, auxiliary towers [szegedy2015going] after the last reduction cell with a weight of $0.4$, label smoothing [szegedy2016rethinking_label_smooth] of $0.1$, AutoAugment [cubuk2018autoaugment] and weight decay of $3\cdot 10^{-4}$.

ImageNet. Our training architecture starts with stem cells that reduce the input image resolution from $224$ to $56$ ($3$ reductions), similar to [liu2018darts]. We then stack $14$ cells: $12$ normal cells and $2$ reduction cells. The reduction cells are placed after the fourth and eighth normal cells. The normal cells start with $46$ channels, as the number of channels is doubled after each reduction cell. We trained the network, with a batch size of $1280$ for $250$ epochs, with one cycle of power cosine learning rate, weight decay of $10^{-4}$ and nesterov-momentum of $0.9$. We add an auxiliary loss after the last reduction cell with a weight of $0.4$. During training, we normalize the input image and crop it with a random cropping factor in the range of $0.08$ to $1$. In addition we use auto-augment and horizontal flipping. During testing, we resize the input image to the size of $256$x$256$ and applying a fixed central crop to the size of $224$x$224$.

Additional datasets. Our additional classification datasets consist of CINIC-10 [darlow2018cinic], CIFAR-100 [cifar100], FREIBURG [Freiburg], SVHN [SVHN] and FashionMNIST [fashionMnist]. Their training scheme was similar to the one used for CIFAR-10, described at 9.3, with some minor adjustments and modifications. For the FREIBURG dataset, we resized the original images from $256$x$256$ to $96$x$96$ and used a batch size of $16$. For CINIC-10, we trained the network for $800$ epochs instead of $1500$, since this dataset is much larger then CIFAR-10. For Fashion-MNIST we edited the learned augmentations regime to fit a dataset of grayscale images.

Cells Learned by XNAS

Figure 9 presents the cells learned by XNAS on CIFAR-10.

Cell depth: When comparing the cell in Figure 9 to other reported NAS cells [noy2019asap, liu2018darts, Real18Regularized, NASNET, snas, PNAS], it is clear visually that XNAS cell is "deeper" in some sense.

We wish to define a metrics for a cell "depth". A cell $C_{k}$ contains four nodes. Each node can be connected to the previous cell’s nodes or to the two previous cells’ outputs $C_{k-2}$, $C_{k-1}$. Let us index the previous cells $C_{k-2}$, $C_{k-1}$ and the cell’s four nodes as $0,\dots,5$ respectively.

Define the depth of each connection in a cell as the index of the node (or previous cell) it came from. A simple metric for a cell depth can be the average depth of its inner connections. Table 4 presents the depth of XNAS and other NAS methods normal cells.

We can see from Table 4 that the XNAS cell is much deeper then a typical NAS cell. This observation could provide a hint about the superior performance of the XNAS cell. Unlike most NAS methods, that usually produce shallow cells, XNAS cell utilizes better the possible degree of freedom of a NAS cell design, yielding a deeper and more complex architecture.