Title: SINGLE PATH ONE-SHOT NEURAL ARCHITECTURE SEARCH WITH UNIFORM SAMPLING Anonymous

Abstract: We revisit the one-shot Neural Architecture Search (NAS) paradigm and analyze its advantages over existing NAS approaches. Existing one-shot method (Bender et al., 2018) , however, is hard to train and not yet effective on large scale datasets like ImageNet. This work propose a Single Path One-Shot model to address the challenge in the training. Our central idea is to construct a simplified supernet, where all architectures are single paths so that weight co-adaption problem is alleviated. Training is performed by uniform path sampling. All architectures (and their weights) are trained fully and equally. Comprehensive experiments verify that our approach is flexible and effective. It is easy to train and fast to search. It effortlessly supports complex search spaces (e.g., building blocks, channel, mixed-precision quantization) and different search constraints (e.g., FLOPs, latency). It is thus convenient to use for various needs. It achieves start-of-the-art performance on the large dataset ImageNet.

1. INTRODUCTION:

Deep learning automates feature engineering and solves the weight optimization problem. Neural Architecture Search (NAS) aims to automate architecture engineering by solving one more problem, architecture design. Early NAS approaches (Zoph et al., 2018; Zhong et al., 2018a; b; Liu et al., 2018a; Real et al., 2018; Tan et al., 2018) solves the two problems in a nested manner. A large number of architectures are sampled and trained from scratch. The computation cost is unaffordable on large datasets.

Recent approaches (Wu et al., 2018a; Cai et al., 2018; Liu et al., 2018b; Xie et al., 2018; Pham et al., 2018; Zhang et al., 2018c; Brock et al., 2017; Bender et al., 2018) adopt a weight sharing strategy to reduce the computation. A supernet subsuming all architectures is trained only once. Each architecture inherits its weights from the supernet. Only fine-tuning is performed. The computation cost is greatly reduced.

Most weight sharing approaches use a continuous relaxation to parameterize the search space (Wu et al., 2018a; Cai et al., 2018; Liu et al., 2018b; Xie et al., 2018; Zhang et al., 2018c) . The architecture distribution parameters are jointly optimized during the supernet training via gradient based methods. The best architecture is sampled from the distribution after optimization. There are two issues in this formulation. First, the weights in the supernet are deeply coupled. It is unclear why inherited weights for a specific architecture are still effective. Second, joint optimization introduces further coupling between the architecture parameters and supernet weights. The greedy nature of the gradient based methods inevitably introduces bias during optimization and could easily mislead the architecture search. They adopted complex optimization techniques to alleviate the problem.

The one-shot paradigm (Brock et al., 2017; Bender et al., 2018) alleviates the second issue. It defines the supernet and performs weight inheritance in a similar way. However, there is no architecture relaxation. The architecture search problem is decoupled from the supernet training and addressed in a separate step. Thus, it is sequential. It combines the merits of both nested and joint optimization approaches above. The architecture search is both efficient and flexible.

The first issue is still problematic. Existing one-shot approaches (Brock et al., 2017; Bender et al., 2018) still have coupled weights in the supernet. Their optimization is complicated and involves sensitive hyper parameters. They have not shown competitive results on large datasets.

This work revisits the one-shot paradigm and presents a new approach that further eases the training and enhances architecture search. Based on the observation that the accuracy of an architecture using inherited weights should be predictive for the accuracy using optimized weights, we propose that the supernet training should be stochastic. All architectures have their weights optimized simultaneously. This gives rise to a uniform sampling strategy. To reduce the weight coupling in the supernet, a simple search space that consists of single path architectures is proposed. The training is hyperparameter-free and easy to converge. This work makes the following contributions.

1. We present a principled analysis and point out drawbacks in existing NAS approaches that use nested and joint optimization. Consequently, we hope this work will renew interest in the one-shot paradigm, which combines the merits of both via sequential optimization. 2. We present a single path one-shot approach with uniform sampling. It overcomes the drawbacks of existing one-shot approaches. Its simplicity enables a rich search space, including novel designs for channel size and bit width, all addressed in a unified manner. Architecture search is efficient and flexible. Evolutionary algorithm is used to support real world constraints easily, such as low latency.

Comprehensive ablation experiments and comparison to previous works on a large dataset (Ima-geNet) verify that the proposed approach is state-of-the-art in terms of accuracy, memory consumption, training time, architecture search efficiency and flexibility.

2. REVIEW OF NAS APPROACHES:

Without loss of generality, the architecture search space A is represented by a directed acyclic graph (DAG). A network architecture is a subgraph a ∈ A, denoted as N (a, w) with weights w.

Neural architecture search aims to solve two related problems. The first is weight optimization,

EQUATION

where L train (•) is the loss function on the training set.

The second is architecture optimization. It finds the architecture that is trained on the training set and has the best accuracy on the validation set, as

EQUATION

where ACC val (•) is the accuracy on the validation set.

Early NAS approaches perform the two optimization problems in a nested manner (Zoph & Le, 2016; Zoph et al., 2018; Zhong et al., 2018a; b; Baker et al., 2016) . Numerous architectures are sampled from A and trained from scratch as in Eq. ( 1). Each training is expensive. Only small dataset (e.g., CIFAR 10) and small search space (e.g, a single block) are affordable.

Recent NAS approaches adopt a weight sharing strategy (Cai et al., 2018; Liu et al., 2018b; Wu et al., 2018a; Xie et al., 2018; Bender et al., 2018; Brock et al., 2017; Zhang et al., 2018c; Pham et al., 2018) . The architecture search space A is encoded in a supernet1 , denoted as N (A, W ), where W is the weights in the supernet. The supernet is trained once. All architectures inherit their weights directly from W . Thus, they share the weights in their common graph nodes. Fine tuning of an architecture is performed in need, but no training from scratch is incurred. Therefore, architecture search is fast and suitable for large datasets like ImageNet.

Most weight sharing approaches convert the discrete architecture search space into a continuous one (Wu et al., 2018a; Cai et al., 2018; Liu et al., 2018b; Xie et al., 2018; Zhang et al., 2018c) . Formally, space A is relaxed to A(θ), where θ denotes the continuous parameters that represent the distribution of the architectures in the space. Note that the new space subsumes the original one, A ⊆ A(θ). An architecture sampled from A(θ) could be invalid in A.

An advantage of the continuous search space is that gradient based methods (Liu et al., 2018b; Cai et al., 2018; Wu et al., 2018a; Véniat & Denoyer, 2018; Xie et al., 2018; Zhang et al., 2018c) is feasible. Both weights and architecture distribution parameters are jointly optimized, as

(θ * , W θ * ) = arg min θ,W

L train (N (A(θ), W )).

(3)

After optimization, the best architecture a * is sampled from A(θ * ). Note that it could be invalid in A. If so, it is validated (e.g., by binarization of θ (Liu et al., 2018b) ). It then inherits the weights from W θ * and is fine-tuned.

Optimization of Eq. ( 3) is challenging. First, the weights of the graph nodes in the supernet depend on each other and become deeply coupled during optimization. For a specific architecture, it inherits certain node weights from W . While these weights are decoupled from the others, it is unclear why they are still effective.

Second, joint optimization of architecture parameter θ and weights W introduces further complexity. Solving Eq. ( 3) inevitably introduces bias to certain areas in θ and certain nodes in W during the progress of optimization. The bias would leave some nodes in the graph well trained and others poorly trained. With different level of maturity in the weights, different architectures are actually non-comparable. However, their prediction accuracy is used as guidance for sampling in A(θ) (e.g., used as reward in policy gradient (Cai et al., 2018) ). This would further mislead the architecture sampling. This problem is in analogy to the "dilemma of exploitation and exploration" problem in reinforcement learning. To alleviate such problems, existing approaches adopt complicated optimization techniques (see Table 7 for a summary). Nevertheless, there lacks a comprehensive evaluation of their effectiveness (Li & Talwalkar, 2019) .

Task constraints Real world tasks usually have additional requirements on a network's memory consumption, FLOPs, latency, energy consumption, etc. These requirements only depends on the architecture a, not on the weights w a . Thus, they are called architecture constraints in this work. A typical constraint is that the network's latency is no more than a preset budget, as Latency(a * ) ≤ Lat max .

(4)

Note that it is challenging to satisfy Eq. (2) and Eq. ( 4) simultaneously for most previous approaches. Some works augment the loss function L train in Eq. (3) with soft loss terms that consider the architecture latency (Cai et al., 2018; Wu et al., 2018a; Xie et al., 2018; Véniat & Denoyer, 2018) . However, it is hard, if not impossible, to guarantee a hard constraint like Eq. (4).

3. OUR SINGLE PATH ONE-SHOT APPROACH:

As analyzed above, the coupling between architecture parameters and weights is problematic. This is caused by joint optimization of both. To alleviate the problem, a natural solution is to decouple the super net training and architecture search in two sequential steps. This leads to the so called one-shot approaches (Brock et al., 2017; Bender et al., 2018) .

In general, the two steps are formulated as follows. Firstly, the supernet weight is optimized as

EQUATION

Compared to Eq. ( 3), the continuous parameterization of search space is absent. Only weights are optimized.

Secondly, architecture searched is performed as

EQUATION

During search, each sampled architecture a inherits its weights from W A as W A (a). The key difference of Eq. ( 6) from Eq. ( 1) and ( 2) is that architecture weights are ready for use. Evaluation of ACC val (•) only requires inference. Thus, the search is very efficient.

The search is also flexible. Any adequate search algorithm is feasible. The architecture constraint like Eq. ( 4) can be exactly satisfied. Search can be repeated many times on the same supernet once trained, using different constraints (e.g., 100ms latency and 200ms latency). These properties are absent in previous approaches. These make the one-shot paradigm attractive for real world tasks.

One problem in Sec. 2 still remains. The graph nodes' weights in the supernet training in Eq.( 5) are coupled. It is unclear why the inherited weights W A (a) are still good for an arbitrary architecture a.

The recent one-shot approach (Bender et al., 2018) attempts to decouple the weights using a "path dropout" strategy. During an SGD step in Eq. ( 5), each edge in the supernet graph is randomly dropped. The random chance is controlled via a dropout rate parameter. In this way, the coadaptation of the node weights is reduced during training. Experiments in (Bender et al., 2018) indicate that the training is very sensitive to the dropout rate parameter. This makes the supernet training hard. A carefully tuned heat-up strategy is used. In our implementation of this work, we also found that the validation accuracy is very sensitive to the dropout rate parameter.

Single Path Supernet and Uniform Sampling. Let us restart to think about the fundamental principle behind the idea of weight sharing. The key to the success of architecture search in Eq. ( 6) is that, the accuracy of any architecture a on a validation set using inherited weight W A (a) (without extra fine tuning) is highly predictive for the accuracy of a that is fully trained. Ideally, this requires that the weight W A (a) to approximate the optimal weight w a as in Eq. ( 1). The quality of the approximation depends on how well the training loss L train (N (a, W A (a))) is minimized. This gives rise to the principle that the supernet weights W A should be optimized in a way that all architectures in the search space are optimized simultaneously. This is expressed as

EQUATION

where Γ(A) is a prior distribution of a ∈ A. Note that Eq. ( 7) is an implementation of Eq. ( 5). In each step of optimization, an architecture a is randomly sampled. Only weights W (a) are activated and updated. So the memory usage is efficient. In this sense, the supernet is no longer a valid network. It behaves as a stochastic supernet (Véniat & Denoyer, 2018) . This is different from (Bender et al., 2018) .

To reduce the co-adaptation between node weights, we propose a supernet structure that each architecture is a single path, as shown in Fig. 3 . Compared to the path dropout strategy in (Bender et al., 2018) , the single path strategy is hyperparameter-free. We compared the two strategies within the same search space (as in this work). Note that the original drop path in (Bender et al., 2018) may drop all operations in a block, resulting in a short cut of identity connection. In our implementation, it is forced that one random path is kept in this case since our choice block does not have an identity branch. We randomly select sub network and evaluate its validation accuracy during the training stage. Results in Fig. 1 show that drop rate parameters matters a lot. Our single path strategy corresponds to using drop rate 1. It works the best, which also verifies the benefits of weight decoupling by our single path strategy.

The prior distribution Γ(A) is important. In this work, we empirically find that uniform sampling is good. This is not much of a surprise. A recent work also finds that purely random search is competitive to several SOTA NAS approaches ( Li & Talwalkar (2019) ). We also experimented with a variant that samples the architectures uniformly according to their constraints, named uniform constraint sampling. Specifically, we randomly choose a range, and then sample the architecture repeatedly until the FLOPs of sampled architecture falls in the range. This is because a real task usually expects to find multiple architectures satisfying different constraints. In this work, we find the uniform constraint sampling method is slightly better. So we use it by default in this paper.

We note that sampling a path according to architecture distribution during optimization is already used in previous weight sharing approaches (Pham et al., 2018; Véniat & Denoyer, 2018; Wu et al., 2018a; Cai et al., 2018; Xie et al., 2018; Zhang et al., 2018c; Yao et al., 2019; Dong & Yang, 2019; Stamoulis et al., 2019) . The difference is that, the distribution Γ(A) is a fixed priori during our training (Eq. ( 7)), while it is learnable and updated (Eq. ( 3)) in previous approaches (e.g. RL (Pham et al., 2018) , policy gradient (Véniat & Denoyer, 2018; Cai et al., 2018) , Gumbel Softmax (Wu et al., 2018a; Xie et al., 2018) , APG (Zhang et al., 2018c) ). As analyzed in Sec. 2, the latter makes the supernet weights and architecture parameters highly correlated and optimization difficult.

Comprehensive experiments in Sec. 4 show that our approach achieves better results than the SOTA methods. Note that there is no such theoretical guarantee that using a fixed prior distribution is inherently better than optimizing the distribution during training. Our better result likely indicates that the joint optimization in Eq. ( 3) is too difficult for the existing optimization techniques.

Supernet Architecture and Novel Choice Block Design. Choice blocks are used to build a stochastic architecture. Fig. 3 illustrates an example case. A choice block consists of multiple architecture choices. For our single path supernet, each choice block only has one choice invoked at the same time. A path is obtained by sampling all the choice blocks.

The simplicity of our approach enables us to define different types of choice blocks to search various architecture variables. Specifically, we propose two novel choice blocks to support complex search spaces. 4 . The main idea is to preallocate a weight tensor with maximum number of channels, and the system randomly selects the channel number and slices out the corresponding subtensor for convolution. With the weight sharing strategy, we found that the supernet can converge quickly.

In detail, assume the dimensions of preallocated weights are (max c out, max c in, ksize). For each batch in supernet training, the number of current output channels c out is randomly sampled. Then, we slice out the weights for current batch with the form Weights[: c out, : c in, :], which is used to produce the output. The optimal number of channels is determined in the search step.

Mixed-Precision Quantization Search. In this work, We design a novel choice block to search the bit widths of the weights and feature maps, as shown in Fig. 5 . We also combine the channel search space discussed earlier to our mixed-precision quantization search space. During supernet training, for each choice block feature bit width and weight bit width are randomly sampled. They are determined in the evolutionary step. See Sec. 4 and Fig. 5 for details.

Evolutionary Architecture Search.:

For architecture search in Eq. ( 6), previous one-shot works (Brock et al., 2017; Bender et al., 2018) use random search. This is not effective for a large search space. This work uses an evolutionary algorithm. Note that evolutionary search in NAS is used in (Real et al., 2018) , but it is costly as each architecture is trained from scratch. In our search, each architecture only performs inference. This is very efficient.

The algorithm is elaborated in Algorithm 1. For all experiments, population size P = 50, max iterations T = 20 and k = 10. For crossover, two randomly selected candidates are crossed to produce a new one. For mutation, a randomly selected candidate mutates its every choice block with probability 0.1 to produce a new candidate. Crossover and mutation are repeated to generate enough new candidates that meet the given architecture constraints. Before the inference of an architecture, the statistics of all the Batch Normalization (BN) (Ioffe & Szegedy, 2015) operations are recalculated on a random subset of training data (20000 images on ImageNet). It takes a few seconds. This is because the BN statistics from the supernet are usually not applicable to the candidate nets. This is also referred in (Bender et al., 2018) . Fig. 2 plots the validation accuracy over generations, using both evolutionary and random search methods. It is clear that evolutionary search is more effective. Experiment details are in Sec. 4.

The evolutionary algorithm is flexible in dealing with different constraints in Eq. ( 4), because the mutation and crossover processes can be directly controlled to generate proper candidates to satisfy the constraints. Previous RL-based (Tan et al., 2018) and gradient-based (Cai et al., 2018; Wu et al., 2018a; Véniat & Denoyer, 2018 ) methods design tricky rewards or loss functions to deal with such constraints. For example, (Wu et al., 2018a ) uses a loss function CE(a, w a ) • α log(LAT(a)) β to balance the accuracy and the latency. It is hard to tune the hyper parameter β to satisfy a hard constraint like Eq. ( 4).

Summary. The combination of single path supernet, uniform sampling training strategy, evolutionary architecture search, and rich search space design makes our approach simple, efficient and flexible. Table 7 in Appendix performs a comprehensive comparison of our approach against previous weight sharing approaches on various aspects. Ours is the easiest to train, occupies the smallest memory, best satisfies the architecture (latency) constraint, and easily supports large datasets. Extensive results in Sec. 4 verify that our approach is the state-of-the-art.

4. EXPERIMENT RESULTS:



Dataset.:

All experiments are performed on ImageNet (Russakovsky et al., 2015) . We randomly split the original training set into two parts: 50000 images for validation (50 images for each class exactly) and the rest as the training set. The original validation set is used for testing, on which all the evaluation results are reported, following (Cai et al., 2018) .

Training. For the training of the supernet and retraining of the best architecture (after evolutionary search) from scratch, we use the same settings (including data augmentation strategy, learning rate schedule, etc.) as (Ma et al., 2018) . The batch size is 1024. Supernet is trained for 120 epochs (150000 iterations) and the best architecture for 240 epochs (300000 iterations). Training uses 8 NVIDIA GTX 1080Ti GPUs.

Search Space: Building Blocks. First, we evaluate our method on the task of building block selection, i.e. to find the optimal combination of building blocks under a certain complexity constraint. Our basic building block design is inspired by a state-of-the-art manually-designed network -ShuffleNet v2 (Ma et al., 2018) . Table 1 shows the overall architecture of the supernet. There are 20 choice blocks in total. Each choice block has 4 candidates, namely "choice 3", "choice 5", "choice 7" and "choice x" respectively (see Fig. 6 in Appendix for details). They differ in kernel sizes and the number of depthwise convolutions. The size of the search space is 4 20 .

We use FLOPs ≤ 330M as the complexity constraint, as the FLOPs of a plenty of previous networks lies in [300, 330] , including manually-designed networks (Howard et al., 2017; Sandler et al., 2018; Zhang et al., 2018b; Ma et al., 2018) and those obtained in NAS (Cai et al., 2018; Wu et al., 2018a; Tan et al., 2018) .

Table 2 shows the results. For comparison, we set up a series of baselines as follows: 1) select a certain block choice only (denoted by "all choice *" entries); note that different choices have different FLOPs, thus we adjust the channels to meet the constraint. 2) Randomly select some candidates from the search space. 3) Replace our evolutionary architecture optimization with random search used in (Brock et al., 2017; Bender et al., 2018) . Results show that random search equipped with our single path supernet finds an architecture only slightly better that random select (73.8 vs. 73.7). It does no mean that our single path supernet is less effective. This is because the random search is too naive to pick good candidates from the large search space. Using evolutionary search, our approach finds out an architecture that achieves superior accuracy (74.3) over all the baselines.

Search Space: Channels. Based on our novel choice block for channel number search, we first evaluate channel search on the baseline structure "all choice 3" (refer to Table 2 ): for each building block, we search the number of "mid-channels" (output channels of the first 1x1 conv in each building block) varying from 0.2x to 1.6x (with stride 0.2), where "k-x" means k times the number of default channels. Same as Sec. 4, we set the complexity constraint FLOPs ≤ 330M . Table 3 (first part) shows the result. Our channel search method has higher accuracy (73.9) than the baselines.

To further boost the accuracy, we search building blocks and channels jointly. There are two alternatives: 1) running channel search on the best building block search result of Sec. 4; or 2) searching on the combined search space directly. In our experiments, we find the results of the first pipeline is slightly better. As shown in Table 3 , searching in the joint space achieves the best accuracy (74.7% acc.), surpassing all the previous state-of-the-art manually-designed (Ma et al., 2018; Sandler et al., 2018) or automatically-searched models (Tan et al., 2018; Zoph et al., 2018; Liu et al., 2018a; b; Cai et al., 2018; Wu et al., 2018a) under the complexity of ∼ 300M FLOPs. Comparison with State-of-the-arts. Results in Table 3 shows our method is superior. Nevertheless, the comparisons could be unfair because different search spaces and training methods are used in previous works (Cai et al., 2018) . To make direct comparisons, we benchmark our approach to the same search space of (Cai et al., 2018; Wu et al., 2018a) . In addition, we retrain the searched models reported in (Cai et al., 2018; Wu et al., 2018a) under the same settings to guarantee the fair comparison.

The search space and supernet architecture in ProxylessNAS (Cai et al., 2018) is inspired by MobileNet v2 (Sandler et al., 2018) and Mnas-Net (Tan et al., 2018) . It contains 21 choice blocks; each choice block has 7 choices (6 different building blocks and one skip layer). The size of the search space is 7 21 . FBNet (Wu et al., 2018a ) also uses a similar search space.

Table 4 reports the accuracy and complexities (FLOPs and latency on our device) of 5 models searched by (Cai et al., 2018; Wu et al., 2018a) , as the baselines. Then, for each baseline, our search method runs under the constraints of same FLOPs or same latency, respectively. Results shows that for all the cases our method achieves comparable or higher accuracy than the counterpart baselines. We also point out that since the target devices in (Cai et al., 2018; Wu et al., 2018a) are different from ours, the reported results may be sub-optimal on our platform.

Furthermore, it is worth noting that all our 10 architectures in Table 4 are searched on the same supernet, justifying the flexibility and efficiency of our approach to deal with different complexity constraints: supernet is trained once and searched multiple times. In contrast, previous methods (Wu et al., 2018a; Cai et al., 2018) Table 5 : Results of mixed-precision quantization search. "kWkA" means k-bit quantization for all the weights and activations. DNAS (Wu et al., 2018b) .

Application: Mixed-Precision Quantization.

We evaluate our method on ResNet-18 and ResNet-34 as common practice in previous quantization works (e.g. (Choi et al., 2018; Wu et al., 2018b; Liu et al., 2018c; Zhou et al., 2016; Zhang et al., 2018a) ). Following (Zhou et al., 2016; Choi et al., 2018; Wu et al., 2018b) , we only search and quantize the res-blocks, excluding the first convolutional layer and the last fully-connected layer. In the search space, choices of weight and feature bit widths include {(1, 2), (2, 2), (1, 4), (2, 4), (3, 4), (4, 4)}. As for channel search, we search the number of "bottleneck channels" (i.e. the output channels of the first convolutional layer in each residual block) in {0.5x, 1.0x, 1.5x}, where "k-x" means k times the number of original channels. The size of the search space is (3 × 6) N = 18 N , where N is the number of choice blocks (N = 8 for ResNet-18 and N = 16 for ResNet-34). Note that for each building block we use the same bit widths for the two convolutions. We use PACT (Choi et al., 2018) as the quantization algorithm.

Table 5 reports the results. The baselines are denoted as kWkA (k = 2, 3, 4), which means uniform quantization of weights and activations with k-bits. Then, our search method runs under the constraints of the corresponding BitOps. We also compare with a recent mixed-precision quantization search approach (Wu et al., 2018b) . Results shows that our method achieves superior accuracy in most cases. Also note that all our results for ResNet-18 and ResNet-34 are searched on the same supernet. This is very efficient. 

:

"Supernet" is used as a general concept in this work. It has different names and implementation in previous approaches.

Figures and Tables:

Figure 2: Evolutionary vs. random architecture search.

Figure 6: Choice blocks used in Sec. 4. From left to right : Choice 3, Choice 5, Choice 7, Choice x.

Figure 10: Searched architectures of joint searching channel size and bit width under BitOPs constraints, see Table 5 for details. (a) -(c) are searched based on Resnet18. (d) -(f) are searched based on Resnet34.

Channel NumberSearch. We propose a new choice block based on weight sharing, as shown in Fig.

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td colspan="2">current input channels (c_in)</td><td>Quantizer</td><td>Feature Bit Width</td></tr><tr><td>Choice Block</td><td/><td/><td/><td>Convolutional Layer</td><td>output channels (c_out)</td><td>Weights</td><td>max output channels</td><td>Convolutional Layer</td><td>Quantizer</td><td>Kernel Weights</td></tr><tr><td>Choice Block</td><td>Choice 1</td><td>Choice 2</td><td>Choice 3</td><td/><td/><td/><td/></tr><tr><td>Choice Block</td><td/><td/><td/><td colspan="2">Weights[:c_out, :c_in, :]</td><td>max input channels</td><td>kernel size</td><td>Weight Bit Width</td></tr><tr><td colspan="4">Figure 3: Choice blocks for our</td><td colspan="4">Figure 4: Choice block for</td><td>Figure 5: Choice block for</td></tr><tr><td colspan="3">single path supernet.</td><td/><td colspan="3">channel number search.</td><td/><td>mixed-precision quantization</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>search.</td></tr></table>

Supernet architecture. CB -choice block. GAP -global average pooling. The "stride" column represents the stride of the first block in each repeated group.

Table content: <table><tr><td>input shape</td><td>block</td><td colspan="3">channels repeat stride</td><td>model</td><td colspan="2">FLOPs top-1 acc(%)</td></tr><tr><td>224 2 × 3 112 2 × 16 56 2 × 64 28 2 × 160 14 2 × 320 7 2 × 640 7 2 × 1024</td><td>3 × 3 conv CB CB CB CB 1 × 1 conv GAP</td><td>16 64 160 320 640 1024 -</td><td>1 4 4 8 4 1 1</td><td>2 2 2 2 2 1 -</td><td colspan="2">all choice 3 all choice 5 all choice 7 all choice x random select (5 times) ∼320M 324M 321M 327M 326M SPS + random search 323M</td><td>73.4 73.5 73.6 73.5 ∼73.7 73.8</td></tr><tr><td>1024</td><td>fc</td><td>1000</td><td>1</td><td>-</td><td>ours (fully-equipped)</td><td>319M</td><td>74.3</td></tr></table>

Results of building block search. SPS -single path supernet.

Table content: <table/>

Results of channel search. * Performances are reported in the form "x (y)", where "x" means the accuracy retrained by us and "y" means accuracy reported by the original paper.

Table content: <table/>

have to train multiple supernets under various constraints. According to Table6, searching is much cheaper than supernet training. Compared with state-of-the-art NAS methods(Wu et al., 2018a;Cai et al., 2018) using the same search space. The latency is evaluated on a single NVIDIA Titan XP GPU, with batchsize = 32. Accuracy numbers in the brackets are reported by the original papers; others are trained by us. All our architectures are searched from the same supernet via evolutionary architecture optimization.

Table content: <table><tr><td>baseline network</td><td>FLOPs</td><td colspan="3">latency top-1 acc(%)</td><td colspan="2">top-1 acc(%)</td><td>top-1 acc(%)</td></tr><tr><td/><td/><td/><td colspan="2">baseline</td><td colspan="2">ours (same FLOPs) ours (same latency)</td></tr><tr><td>FBNet-A (Wu et al., 2018a)</td><td>249M/4.3M</td><td>13ms</td><td colspan="2">73.0 (73.0)</td><td colspan="2">73.2</td><td>73.3</td></tr><tr><td>FBNet-B (Wu et al., 2018a)</td><td>295M/4.5M</td><td>17ms</td><td colspan="2">74.1 (74.1)</td><td colspan="2">74.2</td><td>74.8</td></tr><tr><td>FBNet-C (Wu et al., 2018a)</td><td>375M/5.5M</td><td>19ms</td><td colspan="2">74.9 (74.9)</td><td colspan="2">75.0</td><td>75.1</td></tr><tr><td colspan="2">Proxyless-R (mobile) (Cai et al., 2018) 320M/4.0M</td><td>17ms</td><td colspan="2">74.2 (74.6)</td><td colspan="2">74.5</td><td>74.8</td></tr><tr><td>Proxyless (GPU) (Cai et al., 2018)</td><td>465M/5.3M</td><td>22ms</td><td colspan="2">74.7 (75.1)</td><td colspan="2">74.8</td><td>75.3</td></tr><tr><td/><td/><td/><td colspan="4">Method BitOPs top1-acc(%) Method BitoPs top1-acc(%)</td></tr><tr><td/><td/><td colspan="3">ResNet-18 float point</td><td>70.9</td><td>ResNet-34 float point</td><td>75.0</td></tr><tr><td/><td/><td/><td>2W2A</td><td>6.32G</td><td>65.6</td><td>2W2A</td><td>13.21G</td><td>70.8</td></tr><tr><td/><td/><td/><td>ours</td><td>6.21G</td><td>66.4</td><td>ours</td><td>13.11G</td><td>71.5</td></tr><tr><td/><td/><td/><td>3W3A</td><td>14.21G</td><td>68.3</td><td>3W3A</td><td>29.72G</td><td>72.5</td></tr><tr><td/><td/><td/><td>DNAS</td><td>15.62G</td><td>68.7</td><td>DNAS</td><td>38.64G</td><td>73.2</td></tr><tr><td/><td/><td/><td>ours</td><td>13.49G</td><td>69.4</td><td>ours</td><td>28.78G</td><td>73.9</td></tr><tr><td/><td/><td/><td>4W4A</td><td>25.27G</td><td>69.3</td><td>4W4A</td><td>52.83G</td><td>73.5</td></tr><tr><td/><td/><td/><td>DNAS</td><td>25.70G</td><td>70.6</td><td>DNAS</td><td>57.31G</td><td>74.0</td></tr><tr><td/><td/><td/><td>ours</td><td>24.31G</td><td>70.5</td><td>ours</td><td>51.92G</td><td>74.6</td></tr></table>

Search Cost. Gds -GPU days GPUs. The Table6shows that our approach clearly uses less memory than other two methods because of the single path supernet. And our approach is much more efficient overall although we have an extra search step that costs less than 1 GPU day. Note Table6only compares a single run. In practice, our approach is more advantageous and more convenient to use when multiple searches are needed. As summarized in Table7, it guarantees to find out the architecture satisfying constraints within one search. Repeated search is easily supported.

Table content: <table><tr><td>Search Cost Analysis. The search cost is a</td></tr><tr><td>matter of concern in NAS methods. So we an-</td></tr><tr><td>alyze the search cost of our method and previ-</td></tr><tr><td>ous methods (Wu et al., 2018a; Cai et al., 2018)</td></tr><tr><td>(reimplemented by us). We use the search space</td></tr><tr><td>of our building blocks to measure the memory</td></tr><tr><td>cost of training supernet and overall time cost.</td></tr><tr><td>All the supernets are trained for 150000 iter-</td></tr><tr><td>ations with a batch size of 256. All models</td></tr><tr><td>are trained with 8</td></tr></table>

Structures of searched architectures under FLOPs constraints by using ProxylessNAS search space, see Table 4 for details. Searched result with same latency of Proxyless(GPU) Figure 9: Structures of searched architectures under GPU latency constraints by using ProxylessNAS search space, see Table 4 for details.

Table content: <table><tr><td>MB3 5x5</td><td>MB3 3x3</td><td>Identity</td><td>MB3 5x5</td><td>Identity</td><td>Identity</td><td>MB3 3x3 1.0x</td><td>Identity</td><td>MB3 7x7 1.0x MB3 3x3</td><td>MB3 3x3 1.5x MB3 3x3</td><td>MB3 3x3 Identity 1.5x</td><td>Identity Identity 1.5x</td><td>MB6 7x7 MB3 3x3 1.5x</td><td colspan="2">Identity MB3 7x7 1.5x</td><td>MB3 7x7 Identity 1.5x</td><td>MB3 5x5 MB3 3x3</td><td>MB3 5x5 MB3 5x5</td><td>MB3 5x5 MB3 3x3</td><td>Identity MB3 5x5</td><td>MB3 3x3 MB3 5x5</td><td>MB6 5x5 MB6 3x3</td><td>MB3 3x3 MB6 5x5</td><td/><td>MB3 7x7 MB3 7x7</td><td>MB3 7x7 MB3 3x3</td><td>MB3 7x7 MB6 5x5</td></tr><tr><td colspan="24">MB3 3x3 MB3 3x3 Identity MB3 3x3 Figure 8: (a) Searched result with same latency of FBNet-A MB3 3x3 Identity MB6 5x5 MB3 3x3 MB3 5x5 MB6 3x3 MB6 7x7 MB3 5x5 MB3 3x3 MB6 7x7 MB3 7x7 MB6 5x5 MB3 5x5 MB3 5x5 MB3 5x5 MB3 5x5 MB3 3x3 Identity MB3 3x3 MB3 3x3 MB3 5x5 MB3 5x5 MB6 7x7 MB3 7x7 MB3 3x3 MB3 7x7 MB6 3x3 MB3 5x5 MB3 5x5 MB3 5x5 MB3 7x7 Identity Identity MB6 7x7 Identity Identity MB3 3x3 MB6 7x7 MB3 7x7 Identity MB3 7x7 MB6 3x3 MB3 5x5 MB3 5x5 MB3 3x3 (a) Searched result with same FLOPs of FBNet-A (b) Searched result with same FLOPs of FBNet-B (c) Searched result with same FLOPs of FBNet-C (d) Searched result with same FLOPs of Proxyless-R(mobile) MB6 7x7 MB3 7x7 MB6 7x7 MB3 7x7 MB6 7x7 MB6 7x7 (e) Searched result with same FLOPs of Proxyless (GPU) MB6 5x5 MB6 5x5 MB6 5x5 MB3 5x5 Identity Identity MB3 7x7 MB3 3x3 MB3 5x5 MB3 5x5 Identity MB3 3x3 MB3 7x7 MB3 3x3 MB3 7x7 MB3 5x5 MB3 3x3 (b) Searched result with same latency of FBNet-B and Proxyless-R(mobile) (c) Searched result with same latency of FBNet-C MB3 3x3 MB3 3x3 Identity Identity MB3 3x3 MB6 3x3 MB3 5x5 MB3 5x5 MB6 3x3 MB6 7x7 MB3 3x3 MB6 5x5 MB6 5x5 MB3 7x7 MB6 3x3 MB3 5x5 MB6 5x5 MB6 7x7 MB3 3x3 MB3 7x7 MB3 3x3 Identity MB6 3x3 MB3 5x5 MB3 3x3 MB6 3x3 MB3 7x7 MB3 5x5 MB3 3x3 MB3 7x7 MB6 5x5 MB6 7x7 MB6 3x3 MB6 5x5 MB6 5x5 MB6 7x7 MB3 3x3 Identity Identity Identity Identity Identity MB3 7x7 MB3 7x7 MB6 7x7 MB6 7x7 MB3 7x7 Identity MB6 5x5 MB6 3x3 MB3 3x3 Identity MB6 7x7 MB3 5x5 2W4A 3W4A 4W4A (a) Searched result with 6.21 GBitOPs 1.5x 1.5x 1.5x 0.5x 0.5x 1.0x 1.0x 1.0x (b) Searched result with 13.49 GBitOPs 1.5x 1.0x 1.5x 1.5x 1.5x 1.5x 1.5x 1.5x (c) Searched result with 24.31 GBitOPs 0.6x 1.0x 1.5x 1.5x 1.5x 1.5x 1.5x 0.5x 1.0x 1.0x 1.0x 1.0x 1.0x 1.5x 1.0x 2W2A 1W4A (d) Searched result with 13.11 GBitOPs (e) Searched result with 28.78 GBitOPs 1.5x 1.5x 1.5x 1.0x 1.0x 1.5x 1.0x 0.5x 1.5x 0.5x 1.0x 1.5x 1.5x 1.0x (d) 1W2A 1.5x 1.5x 1.5x 1.5x 1.5x 1.0x 1.5x 1.0x 1.0x 1.0x 1.5x 1.5x 1.5x 1.5x</td><td>MB3 7x7 MB3 7x7 MB3 5x5 MB3 7x7 MB3 7x7 MB3 3x3 MB3 7x7</td><td>1.5x 1.5x 1.5x</td><td>MB3 5x5 MB3 5x5 Identity MB3 5x5 MB3 3x3 MB3 7x7 MB6 3x3</td><td>1.5x 1.5x 1.5x</td><td>MB6 7x7 MB6 7x7 MB6 7x7 MB6 7x7 MB6 7x7 MB6 5x5 MB6 5x5</td></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="12">(f) Searched result with 51.92 GBitOPs</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="5">(a) Block search result</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Choice_7</td><td/><td>Choice_x</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td>1.0x</td><td/><td>0.6x</td><td>1.6x</td><td>1.2x</td><td>1.0x</td><td>1.0x</td><td>0.8x</td><td>1.6x</td><td>1.2x</td><td>1.0x</td><td>1.6x</td><td>1.0x</td><td>1.2x</td><td>1.6x</td><td>0.8x</td><td>0.8x</td><td>1.2x</td><td>1.2x</td><td/><td>1.4x</td><td>1.0x</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="5">(b) Channel search result</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Choice_3</td><td/><td>Choice_5</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td>1.4x</td><td/><td>1.2x</td><td>0.8x</td><td>1.2x</td><td>0.6x</td><td>1.4x</td><td>0.8x</td><td>1.0x</td><td>0.6x</td><td>1.2x</td><td>1.6x</td><td>1.2x</td><td>1.0x</td><td>1.4x</td><td>1.6x</td><td>1.0x</td><td>1.0x</td><td>1.2x</td><td/><td>1.0x</td><td>0.8x</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="9">(c) Block search + channel search result</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
*UPDATE* I have read the other reviews and authors* responses. All the reviewers agree that improving single-shot NAS is an important problem, and that sampling single-paths can be a plausible approach for it that avoids weight coupling. Consequently, I have updated my rating to weak accept. I think the paper can be substantially stronger though. The key claim that set this paper apart from other single-path NAS approaches is that they use a fixed distribution (in particular, the uniform distribution) to sample from unlike others like FBnet who use a trainable distribution. They argue that uniform is parameter-free whereas trainable distributions introduce additional parameters that need to be trained. Their findings motivate a natural follow-up question: could we use a different fixed distribution? Reviewer2 has a similar question in their review. Perhaps a distribution that is weighted according to (some proxy of) how much computational resource the networks take to train? Could such a distribution also be parameter-free and give good benefit over uniform distribution without needing to be updated during supernet training? Such an analysis of the prior distribution will make the paper even stronger. The paper studies a sequential optimization approach to neural architecture search that can provide some benefit over nested or joint approaches. The core challenge in sequential approaches (which first train the weights of a supernetwork; then search through possible architectures which inherit appropriate weights from the supernetwork) is that the weights for a giant network may not be optimal for the weights of a sub-network encountered during subsequent architecture search. The core benefit of such an approach compared to nested approaches is that the subsequent search phase only needs to perform network inference with inherited weights; not train a sub-network from scratch. The primary contribution is to fix a prior distribution over architectures and sample from them when training the supernetwork. This simple fix helps the weights of the giant network be more useful when inherited into any sub-networks during architecture search. The paper will be substantially stronger with a careful study of the choice of the prior distribution and how it affects (a) the rejection sampling step needed to ensure the sampled architectures satisfy complexity constraints, and (b) the performance of the eventual neural architecture search procedure. Another experiment that will be valuable is to rigorously validate the hypothesis that reducing weight coupling in the supernetwork training is crucially linked to improving the downstream architecture search performance. Minor (writing comments): Introduction: *Complex optimization techniques are adopted.* This statement is awkward. Does this paper specifically adopt more complex methods to address the shortcomings of gradient methods. Or, does the community broadly research more complex methods as a consequence (and you are advocating for a return to simpler gradient methods)? Pg5: *we randomly choice a range* -> *choose*