Title: IMPROVING ONE-SHOT NAS BY SUPPRESSING THE POSTERIOR FADING

Abstract: Neural architecture search (NAS) has demonstrated success in automatically designing effective neural network architectures. To improve the efficiency of NAS, previous approaches adopt weight sharing method to force all models share the same set of weights. However, it has been observed that a model performing better with shared weights does not necessarily perform better when trained alone. In this paper, we analyse existing weight sharing one-shot NAS approaches from a Bayesian point of view and identify the posterior fading problem, which compromises the effectiveness of shared weights. To alleviate this problem, we present a practical approach to guide the parameter posterior towards its true distribution. Moreover, a hard latency constraint is introduced during the search so that the desired latency can be achieved. The resulted method, namely Posterior Convergent NAS (PC-NAS), achieves state-of-the-art performance under standard GPU latency constraint on ImageNet. In our small search space, our model PC-NAS-S attains 76.8% top-1 accuracy, 2.1% higher than MobileNetV2 (1.4x) with the same latency. When adopted to the large search space, PC-NAS-L achieves 78.1% top-1 accuracy within 11ms. The discovered architecture also transfers well to other computer vision applications such as object detection and person re-identification.

1. INTRODUCTION:

Neural network design requires extensive experiments by human experts. In recent years, there has been a growing interest in developing algorithmic NAS solutions to automate the manual process of architecture design (Zoph & Le, 2016; Liu et al., 2018a; Zhong et al., 2018; Li et al., 2019; Lin et al., 2019) . Despite remarkable results, early works on NAS (Real et al., 2018; Elsken et al., 2017) are limited to searching only using proxy or subsampled dataset due to the exorbitant computational cost. To overcome this difficulty, (Bender et al., 2018; Pham et al., 2018) attempted to improve search efficiency via sharing weights across models. These approaches utilize an overparameterized network (supergraph) containing every single model, which can be further divided into two categories.

The first category is continuous relaxation method (Liu et al., 2018c; Cai et al., 2018) , which keeps a set of so called architecture parameters to represent the model, and updates these parameters alternatively with supergraph weights. The resulting model is obtained using the architecture parameters at convergence. The continuous relaxation method suffers from the rich-get-richer problem (Adam & Lorraine, 2019) , which means that a better-performed model at the early stage would be trained more frequently (or have larger learning rates). This introduces bias and instability to the search process. The other category is referred to as one-shot method (Brock et al., 2017b; Guo et al., 2019; Bender et al., 2018; Chu et al., 2019) , which divides the NAS procedure into a training stage and a searching stage. In the training stage, the supergraph is optimized along with either dropping out each operator with certain probability or sampling uniformly among candidate architectures. In the search stage, a search algorithm is applied to find the architecture with the highest validation accuracy with shared weights. The one-shot approach ensures the fairness among all models by sampling architecture or dropping out operator uniformly. However, as identified in (Adam & Lorraine, 2019; Chu et al., 2019; Bender et al., 2018) , the problem of one-shot method is that the validation accuracy of the model with shared weights is not predictive to its true performance.

In this paper, we formulate NAS as a Bayesian model selection problem (Chipman et al., 2001) . This formulation is especially helpful in understanding the one-shot approaches in a theoretical way, which in turn provides us a guidance to fundamentally addressing one of the major issues of one-shot approaches. Specially, we show that shared weights are actually a maximum likelihood estimation of a proxy distribution to the true parameter distribution. Most importantly, we identify the common issue of weight sharing, which we call Posterior Fading, i.e., as the number of models in the supergraph increases, the KL-divergence between true parameter posterior and proxy posterior also increases.

To alleviate the Posterior Fading problem, we proposed a practical approach to guide the convergence of the proxy distribution towards the true parameter posterior. Specifically, we divide the training of supergraph into several intervals and maintain a pool of high potential partial models and progressively update this pool after each interval . At each training step, a partial model is sampled from the pool and complemented to a full model. To update the partial model pool, we first generate candidates by extending each partial model and evaluate their potentials, keeping the best performancing ones. The search space is effectively shrunk in the upcoming training interval. Consequently, the parameter posterior get close to the desired true posterior during this procedure. Main contributions of our work is concluded as follows:

• We for the first time analyse one-shot approaches from a Bayesian point of view and identify the associated disadvantage which we call Posterior Fading.

• Guided by the theoretical result, we introduce a novel NAS algorithm fundamentally different from existing one-shot methods, which guides the proxy distribution to converge towards the true parameter posterior.

To examine the effectiveness of our newly proposed method, we benchmark its performance on ImageNet (Russakovsky et al., 2015) against the existing methods. In one typical search space (Cai et al., 2018) , our PC-NAS-S attains 76.8% top-1 accuracy, 0.5% higher and 20% faster than EfficientNet-B0 (Tan & Le, 2019a) , which is the previous state-of-the-art model in mobile setting.

To further demonstrate the advantage of our method, we test it on a larger space and our PC-NAS-L boosts the accuracy to 78.1%.

2. RELATED WORK:

Early neural architecture search (NAS) (Miller et al., 1989; Liu et al., 2018b; Real et al., 2017; Zoph & Le, 2016; Baker et al., 2017a; Wang et al., 2019) methods normally involves with reinforcement learning or neuro-evolution. This type of NAS is typically considered as an agent-based explore and exploit process, where an agent (e.g. an evolution mechanism or a recurrent neural network(RNN)) is introduced to explore a given architecture space with training a network in the inner loop to get an evaluation for guiding exploration. Such methods are computationally expensive and hard to be used on large-scale datasets, e.g. ImageNet.

Recent works (Pham et al., 2018; Brock et al., 2017a; Liu et al., 2018c; Cai et al., 2018) try to alleviate this computation cost via modeling NAS as a single training process of an over-parameterized network that comprises all candidate models, in which weights of the same operators in different models are shared. ENAS (Pham et al., 2018) reduces the computation cost by orders of magnitude, while requires an RNN agent and focuses on small-scale datasets (e.g. CIFAR10). One-shot NAS (Brock et al., 2017b) trains the over-parameterized network along with droping out each operator with increasing probability. Then it use the pre-trained over-parameterized network to evaluate randomly sampled architectures. DARTS (Liu et al., 2018c) additionally introduces a real-valued architecture parameter for each operator and alternately train operator weights and architecture parameters by back-propagation. ProxylessNAS (Cai et al., 2018) binarize the real-value parameters in DARTS to save the GPU cumputation and memory for training the over-parameterized network.

The paradigm of ProxylessNAS (Cai et al., 2018) and DARTS (Liu et al., 2018c) introduce unavoidable bias since operators of models performing well in the beginning will easily get trained more and normally keep being better than other. But they are not necessarily superior than others when trained from scratch. Other relevant works are ASAP (Noy et al., 2019) and XNAS (Nayman et al., 2019) , which introduce pruning during the training of over-parameterized networks to improve the efficiency of NAS. Similar to these approaches, we start with an over-parameterized network and then reduce the search space to derive the optimized architecture. Instead of focusing on the speed-up of training and only pruning by evaluating the architecture parameters, we further improve the rankings of models and evaluate operators directly on validation set.

3. METHODS:

In this section, we first formulate neural architecture search in a Bayesian manner. Utilizing this setup, we introduce the PC-NAS algorithm and analyse its advantage comparing to previous approaches. Finally, we discuss the search algorithm combined with latency constraint. In order to ensure fairness among all models, we set the model prior p(m k ) a uniform distribution.

Under previous setting, we can drive

EQUATION

where 

EQUATION

EQUATION

where -log p(θ|m k ) is a regularization term. Thus minimizing this objective equals to making MLE to p alone (θ|m k , D). When training the supergraph, we sample many models m k , and then train the parameters for these models, which corresponds to a stochastic approximation of the following objective function:

EQUATION

This is equivalent to adopting a proxy parameter posterior as follows:

EQUATION

-log p share (θ|D) = -

EQUATION

Maximizing p share (θ|D) is equivalent to minimizing L share .

We take one step further to assume that the parameters at each layer are independent, i.e.

EQUATION

Due to the independence, we have

EQUATION

where

EQUATION

The KL-divergence between p alone (θ l,o |m k , D) and p share (θ l,o |D) is as follows:

EQUATION

The KL-divergence is just the summation of the cross-entropy of p alone (θ l,o |m k , D) and p alone (θ l,o |m i , D) where i = k. The cross-entropy term is always positive. Increasing the number of architectures would push p share away from p alone , namely the Posterior Fading. We conclude that non-predictive problem originates naturally from one-shot supergraph training, as a typical search space contains a huge 10 21 architectures. Thus if we effectively reduce the number of architectures in (10) during training, the KL divergence would decrease. This is the intuition of our PC-NAS algorithm.

Algorithm 

3.3. POSTERIOR CONVERGENT NAS:

The naive approach to mitigate the posterior fading problem is to limit the number of candidate models inside the supergraph. However, large number of candidates is demanded for NAS to discover promising models. Due to this conflict, we present PC-NAS which adopt progressive search space shrinking. The resulted algorithm divides the training of shared weights into L intervals, where L is the number of mixed operators in the search space. The number of training epochs of a single interval is denoted as T i .

Partial model pool is a collection of partial models. At the l-th interval, a single partial model should contain l -1 selected operators [o 1 , o 2 , ..., o l-1 ]. The size of partial model pool is denoted as P . After the l-th interval, each partial model in the pool will be extended by the N operators in l-th mixop. Thus there are P × N candidate extended partial models with length l. These candidate partial models are evaluated and the top-P among which are used as the partial model pool for the interval l + 1. An illustrative exmaple of partial model pool update is in Fig. 1(b)(c)(d) .

Candidate evaluation with latency constraint We define the potential of a partial model to be the expected validation accuracy of the models which contain the partial model.

EQUATION

)

where the validation accuracy of model m is denoted by Acc(m). We estimate this value by uniformly sampling valid models and computing the average of their validation accuracy using one mini-batch. We use S to denote the evaluation number, which is the total number of sampled models. We observe that when S is large enough, the potential of a partial model is fairly stable and discriminative among candidates. See Algorithm 1 for pseudocode. The latency constraint is imposed by discarding invalid full models when calculating potentials of partial models in the pool. Inspired by warm-up, the first stage is set much more epochs than following stages denoted as T w . The whole PC-NAS process is elaborated in algorithm 2. The number of models in shrunk search space at the interval 100+20×5 = 200 epochs. After searching, we select the best one from the top 5 final partial models and train it from scratch. Similar to EfficientNet and MixNet, We add squeeze-and-excitation (SE) layers (Hu et al., 2018) to our model at the end of each operator. Results with and without SE layers are listed separately in the Table 1 . Since the authors didn't list no SE versions of EfficientNet or MixNet in their original papers, we train them as well as PC-NAS (w/o SE) with exactly the same script and the results are in Table 4 . Table 1 shows the performance of our model on ImageNet. We set our target latency at 10ms according to our measurement of mobile setting models on GPU. Our search result in the small space, namely PC-NAS-S, achieves 76.8% top-1 accuracy under our latency constraint, which is 0.5% higher than EffcientNet-B0 (in terms of absolute accuracy improvement), 1% higher than MixNet-S. If we slightly relax the time constraint, our search result from the large space, namly PC-NAS-L, achieves 78.1% top-1 accuracy, which improves top-1 accuracy by 1.8% compared to EfficientNet-B0, 2.3% compared to MixNet-S. Both PC-NAS-S and PC-NAS-L are faster than EffcientNet-b0 and MixNet-S. We validate our PC-NAS's transferability on two tasks, object detection and person re-identification. We use COCO (Lin et al., 2014) dataset as benchmark for object detection and Market-1501 (Zheng et al., 2015) for person re-identification. For the two dataset, PC-NAS-L pretrained on ImageNet is utilized as feature extractor, and is compared with other models under the same training script. For object detection, the experiment is conducted with the two-stage framework FPN (Lin et al., 2017) .

4.2. IMAGENET RESULTS:

Table 2 shows the performance of our PC-NAS model on COCO and Market-1501. For COCO, our approach significantly surpasses the mAP of MobileNetV2 as well as ResNet50. Compare to the standard ResNet101 backbone, our model achieves comparable mAP quality with almost 1/3 parameters and 2.3× faster speed. Similar phenomena are found on Market-1501. 

4.4. ABLATION STUDY:

Impact of hyperparameters: In this section, we further study the impact of hyperparameters on our method within our small space on ImageNet. The hyperparameters include warm-up, training epochs Tw, partial model pool size P , and evaluation number S. We tried setting Tw as 100 and 150 with fixed P = 5 and S = 900. The resulted models of these two settings show no significant difference in top-1 accuracy (less than 0.1%), shown as in Fig. 2a . Thus we choose warm-up training epochs as 100 in our experiment to save computation resources. For the influence of P and S, we show the results in Fig. 2a . It can be seen that the top-1 accuracy of the models found by PC-NAS increases with both P and S. Thus we choose P = 5, S = 900 in the experiments for better performance. we did not observe significant improvement when further increasing these two hyperparameters.

Effectiveness of shrinking search space::

To assess the role of space shrinking, we train the supergraph of our large space using One-Shot (Brock et al., 2017b) method without any shrinking of the search space. Then we conduct model search on this supergraph by progressively updating a partial model pool in our method. The resulted model using this setting attains 77.1% top-1 accuracy on ImageNet, which is 1% lower than our PC-NAS-L. We further double the value of P or S, and the results are listed in Table 3 . From these results, we could conclude that our search method alone already lead to impressive performance. And our space shrinking training strategy improves model ranking and brings extra 0.7%-1% accuracy boost.

We add another comparison as follows. First, we select a batch of models from the candidates of our final pool under small space and evaluate their stand alone top-1 accuracy. Then we use One-Shot to train the supergraph also under small space without shrinking. Finally, we shows the model rankings of PC-NAS and One-Shot using the accuracy obtained from inferring the models in the supergraphs trained with the two methods. The difference is shown in Fig. 2b , the pearson correlation coefficients between stand-alone accuracy and accuracy in supergraph of One-Shot and PC-NAS are 0.11 and 0.92, thus models under PC-NAS's space shrinking can be ranked by their accuracy evaluated on sharing weights much more precisely than One-Shot.

Effectiveness of our search method::

To investigate the importance of our search method, we utilize Evolution Algorithm (EA) to search for models with the above supergraph of our large space trained with One-Shot. The top-1 accuracy of discovered model drops furthur to 75.9% accuracy, which is 2.2% lower than PC-NAS-L . We implement EA with population size 5, aligned to the value of pool size P in our method, and set the mutation operation as randomly replace the operator in one mixop operator to another. We constrain the total number of validation images in EA the same as ours. The results are also shown in Table 3 .

5. CONCLUSION:

In this paper, a new architecture search approach called PC-NAS is proposed. We study the conventional weight sharing approach from Bayesian point of view and identify a key issue that compromises the effectiveness of shared weights. With the theoretical motivation, a practical method 

:



Figures and Tables:

Figure 1: One example of search space(a) and PC-NAS process(b)(c)(d).Each mixed opperator consists of N (=3 in this figure) operators. However, only one operator in each mixop is invoked at a time for each batch. In (b), partial models 1 and 2 in the pool consist of choices in mixop 1 and 2. We extend these 2 partial models to one mixop 3. 6 extended candidate models are evaluated and ranked in(c). In (d), the new pool consists of the top-2 candidate models ranked in (c).

3.1 A PROBABILISTIC SETUP FOR MODEL UNCERTAINTYSuppose we have K different models M = {m 1 , ..., m K } under consideration for data D, and p(D|θ k , m k ) describes the probability density of data D given model m k and its associated parameters θ k . The Bayesian approach proceeds by assigning a prior probability distribution p(θ k |m k ) to the parameters of each model, and a prior probability p(m k ) to each model.

Training based on partial model pool The training iteration of the supergraph along with the partial model pool has two steps. First, for a partial model from the pool, we randomly sample the missing operator {o l+1 , o l+2 , ..., o L } to complement the partial model to a full model. Then we optimize θ using the sampled full model and mini-batch data. Initially, the partial model pool is empty. Thus the supergraph is trained by uniformly sampled models, which is identical to previous one-shot training stage. After the initial training, all operators in the first mixop are evaluated. The top P operators form the partial model pool in the second training stage. Then, the supergraph resumes training and the training procedure is identical to the one discussed in last paragraph.

Figure 2: (a): Influence of warm-up epochs T w , partial model pool size P , and evaluation number S to the resulted model. (b): Comparison of model rankings for One-Shot (left) and PC-NAS (right).

.2 NETWORK ARCHITECTURE SELECTION IN A BAYESIAN POINT OF VIEWWe constrain our discussion in the setting which is frequently used in NAS literature for simplicity. As a building block of our search space, a mixed operator (mixop), denoted by O = {O 1 . . . , O N }, contains N different choices of candidate operators O i for i = 1, . . . N in parallel. The search space is defined by L mixed operators (layers) connected sequentially interleaved by downsampling as in Fig.1(a). The network architecture (model) m is defined by a vector [o 1 , o 2 , ..., o L ], o l ∈ O representing the choice of operator for layer l. The parameter for the operator o at the l-th layer is denoted as θ lo . The parameters of the supergraph are denoted by θ which includes {θ lo |l ∈ {1, 2, ..., L}, o ∈ O}. In this setting, the parameters of each candidate operator are shared among multiple architectures. The parameters related with a specific model m k is denoted as θ k = θ 1,o1 , θ 2,o2 , ..., θ L,o L , which is a subset of the parameters of the supergraph θ. Obtaining the p alone (θ k |m k , D) or a MLE of it for every model is computationally intractable. Therefore, the one-shot method trains the supergraph by dropping out each operator(Brock et al., 2017b)  or sampling different architectures(Bender et al., 2018;Chu et al., 2019) and utilize the shared weights to evaluate single model. In this work, we adopt the latter training paradigm while the former one could be easily generalized. Suppose we sample a model m k and optimize the supergraph with a mini-batch of data based on the objective function L alone :

Table content: <table><tr><td>3</td></tr></table>

1 Potential: Evaluating the Potential of Partial Candidates Lat then continue dump samples that don't satisfy the latency constraint end if acc = Acc(m * , D val ) inference m * for one batch and return its accuracy

Table content: <table><tr><td>Inputs: G(supergraph), L(num of mixops in G), m (partial candidate), Lat(latency constraint),</td></tr><tr><td>S(evaluation number), D val (validataion set)</td></tr><tr><td>Scores = ∅</td></tr><tr><td>for i = 1 : S do</td></tr><tr><td>m  Scores.append(acc) save accuracy</td></tr><tr><td>end for</td></tr><tr><td>Outputs: Average(Scores)</td></tr></table>

PC-NAS' Imagenet results compared with state-of-the-art methods in the mobile setting.

Table content: <table><tr><td>model</td><td>space</td><td colspan="4">params latency top-1 top-1(+SE)</td></tr><tr><td>MobileNetV2 1.4x (Sandler et al., 2018)</td><td>-</td><td>6.9M</td><td>10ms</td><td>74.7%</td><td>-</td></tr><tr><td>AmoebaNet-A (Real et al., 2018)</td><td>-</td><td>5.1M</td><td>23ms</td><td>74.5%</td><td>-</td></tr><tr><td>PNASNet (Liu et al., 2018a)</td><td>5.6x10 14</td><td>5.1M</td><td>25ms</td><td>74.2%</td><td>-</td></tr><tr><td>FBNet-C (Wu et al., 2018)</td><td>10 21</td><td>5.5M</td><td>-</td><td>74.9%</td><td>-</td></tr><tr><td>MnasNet (Tan et al., 2018)</td><td>-</td><td>4.4M</td><td>11ms</td><td>74.8%</td><td>76.1%</td></tr><tr><td>ProxylessNAS-gpu (Cai et al., 2018)</td><td>7 21</td><td>7.1M</td><td>8ms</td><td>75.1%</td><td>-</td></tr><tr><td>MixNet-S (Tan &amp; Le, 2019b)</td><td>-</td><td>4.1M</td><td>13 ms</td><td>-</td><td>75.8%</td></tr><tr><td>EfficientNet-B0 (Tan &amp; Le, 2019a)</td><td>-</td><td>5.3M</td><td>13 ms</td><td>-</td><td>76.3%</td></tr><tr><td>PC-NAS-S</td><td>10 21</td><td>5.1M</td><td>10 ms</td><td>76.1%</td><td>76.8%</td></tr><tr><td>PC-NAS-L</td><td>20 21</td><td>15.3M</td><td>11 ms</td><td>77.5%</td><td>78.1%</td></tr></table>

Performance Comparison on COCO and Market-1501

Table content: <table><tr><td>backbone</td><td colspan="4">params latency COCO mAP Market-1501 mAP</td></tr><tr><td>MobileNetV2</td><td>3.5M</td><td>7ms</td><td>31.7</td><td>76.8</td></tr><tr><td>ResNet50</td><td>25.5M</td><td>15ms</td><td>36.8</td><td>80.9</td></tr><tr><td>ResNet101</td><td>44.4M</td><td>26ms</td><td>39.4</td><td>82.1</td></tr><tr><td>PC-NAS-L</td><td>15.3M</td><td>11ms</td><td>38.5</td><td>81.0</td></tr><tr><td colspan="2">4.3 TRANSFERABILITY OF PC-NAS</td><td/><td/><td/></tr></table>

Comparison of different one-shot search methods

Table content: <table><tr><td>training method</td><td>search method</td><td>top-1 acc</td></tr><tr><td>PC-NAS</td><td>PC-NAS</td><td>78.1%</td></tr><tr><td>One-Shot</td><td>PC-NAS</td><td>77.1%</td></tr><tr><td>One-Shot</td><td>PC-NAS (P = 10)</td><td>77.4%</td></tr><tr><td>One-Shot</td><td>PC-NAS (S = 1800)</td><td>77.2%</td></tr><tr><td>One-Shot</td><td>EA</td><td>75.9%</td></tr></table>

Accuracy comparison trained with exactly the same script mitigate the issue. Experimental results demonstrate the effectiveness of our method, which achieves state-of-the-art performance on ImageNet, and transfers well to COCO detection and person re-identification too.

Table content: <table><tr><td>models</td><td>top-1 acc</td></tr><tr><td>EfficientNet-B0 (w/o SE)</td><td>74.1%</td></tr><tr><td>MixNet-S (w/o SE)</td><td>74.6%</td></tr><tr><td>PC-NAS-S (w/o SE)</td><td>76.1%</td></tr><tr><td>PC-NAS-L (w/o SE)</td><td>77.5%</td></tr></table>

Peer review (iclr2020):
Let me start by saying I am not an expert in architecture search, and putting lowest confidence accordingly. Nevertheless, I have concerns about this paper. While the basic idea of progressive search is reasonable, it is not tightly coupled to the Bayesian argument the authors use to motivate it. This argument makes some unnatural assumptions (e.g. layers are independent); and the authors do not give any rigorous analysis, either theoretical or empirical, of how their progressive search method mollifies the posterior fading problem they discuss. IMO, the whole Bayesian setup makes the motivation unnecessarily complex, and is math for maths sake, rather than for clarification. The authors do try to show that the final results are better (which isn*t the same thing as saying that the method is fixing posterior fading); but I don*t think these experiments are convincing. In particular, the authors seem to use different regularizers than there competitors, and it is not clear where from where the performance gains come.