{'fraction_non_alphanumeric': 0.040586184353889734, 'fraction_numerical': 0.013592285901067772, 'mean_word_length': 4.974450772986168, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics

This work targets designing a principled and unified training-free framework for Neural Architecture Search (NAS), with high performance, low cost, and in-depth interpretation. NAS has been explosively studied to automate the discovery of top-performer neural networks, but suffers from heavy resource consumption and often incurs search bias due to truncated training or approximations. Recent NAS works start to explore indicators that can predict a network's performance without training. However, they either leveraged limited properties of deep networks, or the benefits of their training-free indicators are not applied to more extensive search methods. By rigorous correlation analysis, we present a unified framework to understand and accelerate NAS, by disentangling"TEG"characteristics of searched networks - Trainability, Expressivity, Generalization - all assessed in a training-free manner. The TEG indicators could be scaled up and integrated with various NAS search methods, including both supernet and single-path approaches. Extensive studies validate the effective and efficient guidance from our TEG-NAS framework, leading to both improved search accuracy and over 2.3x reduction in search time cost. Moreover, we visualize search trajectories on three landscapes of"TEG"characteristics, observing that while a good local minimum is easier to find on NAS-Bench-201 given its simple topology, balancing"TEG"characteristics is much harder on the DARTS search space due to its complex landscape geometry. Our code is available at https://github.com/VITA-Group/TEGNAS.

Despite the principled automation, NAS still suffers from heavy consumption of computation time and resources. Most NAS methods mainly leverage the validation set and conduct accuracy-driven architecture optimization. Therefore, frequent training and evaluation of sampled architectures become a severe bottleneck that hinders both search efficiency and interpretation. A super-network is extremely slow to be trained till converge [17] with even many effective heuristics • Wuyang Chen, Xinyu Gong for channel approximations or architecture sampling [18], [19]. Approximated proxy inference such as truncated training/early stopping can accelerate the search, but is observed to introduce severe search bias [10], [20], [21]. People recently address this problem by proposing training-free NAS. Indicators like covariance of sample-wise Jacobian [1], Neural Tangent Kernel [2], and "synflow" [3] are found to highly correlate with network's accuracy even at initialization (i.e., no gradient descent). This significantly reduces the search cost. However, these works only validated a few highly customized search approaches, and leveraged limited properties of deep networks in an empirical or adhoc way. Mellor et al. [1] only considered the "local linear map" defined by the covariance of sample-wise Jacobian, and only studied the random search method. Abdelfattah et al. [3] mainly leveraged "synflow" proposed by previous pruning literature [22] while relying on a warm-up stage. Chen et al. [2] considered two aspects (trainability and expressivity) and integrated two indicators, but still have to leverage highly customized supernet pruning method and cannot extend to other non-supernet NAS search methods. Moreover, these training-free indicators still only pursue final search performance, and we can hardly benefit more about interpretation and understanding of the search trajectory and different search spaces.
In contrast, we target on designing a unified and explainable training-free NAS framework that is (i) "search method agnostic", i.e., can be scaled up to a broad variety of popular search algorithms; (ii) "interpretable", i.e., can help understand search behaviors on different landscapes of architecture spaces. We first propose to disentangle the network's characteristics into three distinct aspects: Trainability, arXiv:2108.11939v1 [cs.LG] 26 Aug 2021 Expressivity, Generalization, or "TEG" for short. All three could be assessed with training-free indicators, and our studies demonstrate their strong correlations with network's training or test accuracy. Further, across various network operator types and topologies, they show complementary preferences, together leading to a comprehensive picture. Extensive studies validate the effective and efficient guidance from our TEG-NAS framework, with both improvements on search accuracy and over 2.3× reduction on search time cost. More importantly, we for the first time visualize the search trajectory on architecture landscapes from different search spaces, thanks to our proposed TEG dimensions that disentangles different aspects of the searched model performance and can be efficiently quantified. For example, we find that a good local optimum is easier to find on NAS-Bench-201 [23] which has simpler topologies. However, it is much harder for a search method to balance TEG properties on the DARTS space with complex architecture landscapes. We summarize our contributions as: • We perform a rigorous correlation analysis of three disentangled "TEG" properties against network's training and test accuracy, and how changes made to an architecture will affect these aspects. The rest of the paper is organized as follows. After reviewing recent advanced methods for efficient NAS and topics in Deep Learning theory (Section 2), in Section 3 we first introduce our motivation and background in analyzing trainability/expressivity/generalization of deep networks. Definitions and architecture inductive biases of three theorygrounded metrics will be explained, and we will demonstrate that disentangling different aspects of neural architectures leads to a better ranking prediction of networks from a search space. After validating different preferences of our three training-free metrics on network architectures, in Section 4.2 we propose a unified and interpretable NAS framework that does not require any gradient descent training. Our NAS framework can not only be easily integrated into recent popular NAS methods (reinforcement learning, evolution, supernet), but also reflect a novel visualization of architecture landscapes. This contributes to both accelerated high-performance NAS methods and interpretable tools for analyzing NAS search space. We show our final results in Section 5, where we studied the search accuracy and time cost on both NAS-Bench-201 [23] and DARTS space.
The preliminary version of this work has been published in [2], and we have made significant improvements over it. First, in the main method section, we will introduce a missing part in our ICLR version -a training-free indicator for the generalization (Sec. 3.3). As generalization is a different property of deep networks besides trainability and expressivity, we will demonstrate its strong indication of network performance, its distinct architecture preference (Sec. 4.1), and its contribution to the final search results. Second, this version of training-free NAS is no longer a highly customized algorithm, but a unified and generally adoptable framework, which will be verified in three popular NAS search methods in our experiments (Sec. 5). All three NAS methods will benefit from strong search guidance and significant time cost reduction after being inter grated with our general framework. Finally, our new work will facilitate search space visualization and contribute to a novel interpretability study of the NAS search process. By tracking and projecting the search trajectory along the three proposed TEG dimensions, we can observe distinct landscape patterns from simple to complex search spaces, which will provide insights for understanding and designing NAS search spaces.

Neural Architecture Search
Most NAS works suffer from heavy search costs. Samplingbased methods [10], [24], [25], [26] achieve accurate network evaluations, but the truncated training imposes bias on the architecture rankings. The one-shot super network [17], [19], [27], [28] can share parameters to sub-networks and greatly accelerate the evaluations, but it is hard to optimize [29] and suffers from poor correlation between supernet accuracy and its sub-networks' [30]. In all, there is no clear one-winner method across the variety.

Efficient and Training-free NAS
Recent NAS works start focusing on reduced training or even training-free search. EcoNAS [31] investigated different ad-hoc proxies (input size, model size, training samples, epochs, etc.) to reduce the training cost. Mellor et al. [1] for the first time proposed a training-free NAS framework, which empirically leverages the correlation between samplewise Jacobian to rank architectures. However, why did the Jacobian work was not clearly explained and demonstrated. Abdelfattah et al. [3] studied different training-free indicators, and leveraged "synflow" from pruning [22] as the main ranking metric. Chen et al. [2] studied two theory-inspired indicators and combined with supernet pruning for further efficiency. However, these methods either leveraged adhoc or limited theory-driven properties of deep networks, or the benefits of their training-free strategies are tied to some specific search methods. In contrast, we hope to explore a comprehensive set of deep network properties, and further propose a unified training-free framework for various existing NAS methods.

Trainability, Expressivity, and Generalization
Numerous indicators in the deep learning theory field have been proposed to study various aspects of deep networks. Neural tangent kernel (NTK) is proposed to characterize the gradient descent training dynamics of wide networks [32], [33]. It was also proved that wide networks evolve as linear models under gradient descent [34]. Xiao et al. [35] further propose to decouple the network's trainability and generalization. Meanwhile, a network's expressivity can be measured as the number of linear regions separated in the input space [36], [37], [38], [39]. Many works also try directly probe network's generalization from various training statistics or network parameters [40], [41], [42].

DISENTANGLING TRAINABILITY, EXPRESSIVITY, AND GENERALIZATION OF DEEP NETWORKS
Trainability, expressivity, and generalization are three important, distinct, and complementary properties to characterize and understand neural networks [35], [38], [40]. Typically, a deep network achieves high performance when: 1) it can produce a loss landscape that is easily trainable with gradient descent, 2) it can represent sufficiently complex functions, 3) it can learn representation transferable to unseen examples, instead of just memorizing training data.

Trainability
Training deep networks requires optimizing highdimensional non-convex loss functions. In practice, gradient descent often finds the global or good local minimum. However, many expressible networks are not easily learnable. For example, a deep stack of convolutional layers (e.g. Vgg [4]) is much harder to train than networks with skip connections (ResNet [6], DenseNet [43], etc.), even the former could equip a larger number of parameters. The trainability of a neural network studies how effective it can be optimized by gradient descent [44], [45], [46]. Architecture Bias on Trainability: A network's architecture can control how effectively the gradient information can flow through it. These topological properties might control the amount of information that can be learned by networks. Preserving the gradient flow is found to be essential during network pruning, even at initialization [22], [47]. Skip connections also have a significant impact on the sharpness/flatness of the loss landscapes [48]. Therefore, we hypothesize that certain aspects of trainability can be characterized just by the architecture at its initialization.
Conditioning of NTK: To characterize the training dynamics of wide networks, Neural tangent kernel (NTK) is proposed [34], [49], [50], defined as: where J(x) is the Jacobian evaluated at a point x. Xiao et al. [35] measures the trainability of networks by studying the spectrum and conditioning ofΘ: is the expected outputs of a wide network, λ i are the eigenvalues ofΘ(x train , x train ), x train and y train are drawn from the training set D train . Eq. 3 indicates that different time is needed to learn the i-th eigenmode, and thus we can conclude that the more diverse the learning speeds of different eigenmodes are, the more difficult the network can be optimized. We are therefore motivated to use the empirical condition number of NTK to represent trainability: where network parameters θ are drawn from Kaiming normal initialization N (0, 2 N l ) (N l is the width at layer l) [51], and thusκ is calculated at network's initialization. As shown in Figure 1,κ is negatively correlated with both the network's training and test accuracy, with the Kendall-tau correlation as −0.59. Therefore, minimizing theκ during the search will encourage the discovery of architectures with high performance.

Expressivity
Recent works try to explain the success of deep networks by their ability to approximate complex functions, quantified by various complexity measures [52], [53]. The more expressible the network is, the more efficient it can fit the training data. In the case of ReLU networks that compute piecewise linear functions, the number of distinct linear regions is a natural measure of such expressivity. The composition of ReLU leads the input space partitioned into distinct pieces (i.e. linear regions). Therefore, the density of linear regions serves as a convenient proxy for the complexity of the network [36], [38], [39], [54].
Architecture Bias on Expressivity: It was proved that networks with random Gaussian initialization can embed the training data in a distance-preserving manner [55]. Hanin et al. [54] show that the number of activation patterns for ReLU networks is tightly bounded by the total number of neurons both at initialization and during training, and empirically showed that the number of regions stays roughly constant during training [38]. Therefore, network architecture itself has a strong inductive bias on its expressivity.

Complexity of Linear Regions:
We first introduce the definition of activation patterns and see how it is connected to the number of linear regions in input space.

Definition 1 of [39] (Activation Patterns as the Linear Regions)
Let N be a ReLU CNN. An activation pattern of N is a function P from the set of neurons to {1, −1}, i.e., for each neuron z in N , we have P (z) ∈ {1, −1}. Let θ be a fixed set of parameters (weights and biases) in N , and P be an activation pattern. The region corresponding to P and θ is where z(x 0 ; θ) is the pre-activation of a neuron z. Let R N ,θ denote the number of linear regions of N at θ, i.e., R N ,θ := #{R(P ; θ) : R(P ; θ) = ∅ for some activation pattern P }.
Eq. 5 tells us that a linear region in the input space is a set of input data x 0 that satisfies a certain fixed activation pattern P (z), and therefore the number of linear regions R N ,θ measures how many unique activation patterns that can be divided by the network.
Since the input space is recursively partitioned by ReLU as the layers go deeper, and the composition of piecewise   We are therefore motivated to use the empirical number of linear regions to represent expressivity: As shown in Figure 1,R is positively correlated with both the network's training and test accuracy. Moreover, we observe thatR has a stronger correlation with training over test accuracy, which validates thatR indicates how well a network fits the training data, but not its generalizability.

Generalization
Typically, the generalization error is defined as the risk of the model over the underlying data distribution D. A model chosen from a very complex family of functions can essentially fit all the training data, but memorization cannot guarantee the accurate association of unseen examples with seen ones. That makes generalization a distinct notion from trainability ("optimization") and expressivity ("memorization"), since generalization focuses on how well a model can transfer the information from seen to unseen data. Architecture Bias on Generalization: With even random initialization, network architecture alone could have a strong inductive bias to its generalization error. Network architectures of different complexity or sparsity, without learning any weight parameters, are found to be able to encode solutions for a given task [56], [57]. Bhardwaj et al. [58] formally established a link between the structure of CNN architectures (depths, widths, number of skip connections, etc.) and their generalization errors. More importantly, inductive bias from certain architecture patterns (e.g. graph-based representation [59]) can even transfer across different types of networks (MLPs, CNNs, ResNets, etc.) and different tasks (CIFAR-10, ImageNet, etc.). Same in our work, we decouple the architecture from the network weights, and focus only on the aspect of "weight-agnostic" generalization, which is impacted by just the network architecture.
NTK Kernel Regression: Previous works [34], [35] showed that at time t during gradient descent training with an MSE loss, the expected outputs of an infinite wide network evolve as: Studying the evolution of µ t (x test ) in Eq. 7 along the training iteration t can characterize the generalization performance of deep networks. However, the infinite width is not directly applicable in real-life scenarios, and we want to estimate the generalization at a network's initialization. Therefore in our work, we choose to empirically estimate the generalization by calculating the test MSE error of a network's NTK kernel regression: Θ L indicates the NTK evaluated only for the last layer of the deep network. Eq. 8 tries to associate x test with x train via NTK kernel regression, and transfer the given training labels y train to the test data. A deep neural network will fail to generalize if its predictionŷ test becomes data-independent, and the MSE in Eq. 9 will become large. Note that we are not directly predicting a network's converged generalization at its initialization. Instead, we use MSE to compare different networks and study how it would be affected by different architectures. Adopting MSE also follows the convention that NTK is also derived under the squared loss [32], [60]. As further demonstrated in Figure 1, MSE shows strong negative correlation with both the network's training accuracy and test accuracy. More importantly, it has a stronger correlation with the test than the training accuracy. This precisely validates that MSE represents how well a network generalizes, but not memorization of the training data.
At this moment we disentangled the network's performance into three distinct properties. In the next section, we present our unified and interpretable TEG-NAS strategy.

TEG-NAS: A UNIFIED AND INTERPRETABLE NAS FRAMEWORK
Our core motivation is to provide a unified training-free framework for NAS of both high performance and low cost. We also enable the interpretability of NAS by visualizing the search trajectory on the architecture landscapes.

How Architecture Affectsκ,R, and M SE
Despite the strong correlations and different preferences over training or testing accuracy we observe in Figure 1, it is still unknown whether each individual aspect of threetrainability, expressivity, generalization -is necessary for a deep network to be of high performance. This analysis is also missing in previous works [2], [35]. Before we directly adopt our disentangled TEG properties to NAS search, we must study how changes ofκ,R, MSE could be reflected on network architectures, and how network's operator types or topology will affect its trainability, expressivity, and generalization. Otherwise, if they share the same preference on selecting architectures, picking any one of them will guide the search towards similar results.
Architecture Exclusively Selected byκ,R, MSE Trainability, expressivity, and generalization may have different preferences over network's operator types and topology. This motivates us to summarize architectures that are exclusively selected byκ,R, MSE. We first measure the thresholds T κ , T R , T MSE that filter top 10% architectures out of the search space A, ranked byκ,R, and MSE, respectively. We define the following three subsets of architectures, with any two out of three having an empty intersection: We study three subsets of architectures in terms of both operator and topology, shown in Figure 2. For operator types, the ratio of convolution (1 × 1 and 3 × 3) operators in A κ is lower than those of A R and A MSE , indicating operators with a heavy number of parameters may not friendly for optimization. In contrast, A R and A MSE favor more convolution layers, benefiting to data fitting. For network topology, the averaged depth 1 of architectures in A κ is much lower than those in A R , since shallow networks are easier to train [35] Fig. 3: "None" operator jeopardize the architecture's trainability, expressivity, and generalization. By replacing "none" with "skip connect" or "conv1×1", the bad trainability or expressivity can be addressed, leading to better test accuracy.

Case Study
One failure reason for a bad architecture is the exist of "none" (or "zero") operator, which completely breaks the feed-forward and gradient flow. We show one case in Figure 3. When there is a "none" exist, both trainability and expressivity are bad, leading to poor test accuracy. By switching into "skip connect" or "conv1 × 1", the bad trainability or expressivity are addressed, leading to better test accuracy.

A Unified Training-free NAS Framework
Different preferences ofκ,R, and MSE on network's operators and topology validate their potential of guiding the 1. Depth of a cell is defined as the number of connections on the longest path from input to the output [61]

Comparison with Prior Works
• Mellor et al. [1] only leveraged sample-wise correlation of Jacobian, with no detailed explanation of which aspect (trainability/expressivity/generalization) this metric represents. Moreover, they only leveraged Random Search on NAS-Bench-201, without studying more NAS methods and search spaces. • Abdelfattah et al. [3] mainly leveraged "synflow" metric equipped with "warm-up" or "move proposal" search strategy, which is related to trainability. However, they still have to use trained models for proxy inference during the search. • Chen et al. [2] built their framework on top of a super-net based approach, and strongly rely on a highly customized super-net pruning strategy. We evaluate their method without pruning (shown in Table 2) and observed inferior performance.

Visualizing Search Process on Different Architecture Landscapes
It has been a missing part in the NAS community to visualize the search process on architecture landscapes from different search spaces. Several bottlenecks hinder this analysis: 1) evaluation via truncated training still suffers from heavy computation cost, making the architecture landscape intractable to characterize; 2) the truncated accuracy or loss value is noisy, making the trade-off of exploration-exploitation of the search process hard to observe. We leverage the Reinforcement Learning as the example, and take pioneering steps to conduct such analysis: • To explore the global and local geometry of the architecture landscapes, at search step t we spawn a parent architecture into two children, and proceed the search of these two children with different randomness. • We collect the trajectory of architectures from two children, and project the high-dimensional architecture space into a 2D plane via PCA. We perform these analysis at early and late search steps on both NAS-Bench-201 space [23] and DARTS search space [17] (see search space details in Section 5), shown in Figure 4. Our observations are summarized as follows: • On NAS-Bench-201, the search can land in areas whereκ t , R t , and MSE t are all good. Although some areas (e.g. area "A" in early NAS-Bench-201) enjoy local minimal on one of the three aspects, the search will proceed beyond it due to its inferiority on the other two properties. • Spawning at both early and late search stage, two children from NAS-Bench-201 land in the same area in the end. This is probably because of the simple operator types and topology from the design of NAS-Bench-201 (see details in Section 5.3 and original paper [23]). • DARTS space is associated with much more complex architecture landscapes. Children spawned from both early and late stage may land in different areas, with a barrier (or a valley) on their interpolation (orange dashed line). This complex landscape introduce significant challenge to balance and trade-offκ t ,R t , and MSE t for NAS search, with even noisy signals. The impact of our landscape analysis lies in two folds: 1) For designing NAS algorithms: visualizing the search process can reveal the quality and stability of the search via different spawning and randomness. 2) For designing search spaces: [62], [63], visualizing the architecture landscapes can help study the complexity and geometry of the search space.

EXPERIMENTS
In this section, we evaluate our TEG-NAS framework on two search spaces: NAS-Bench-201 [23] and DARTS [17]. Training protocols are summarized in our supplement. For DARTS space, we conduct experiments on both CIFAR-10 and ImageNet (Section 5.4). For NAS-Bench-201, we test all three supported datasets (CIFAR-10, CIFAR-100, ImageNet-16-120 [67]) in section 5.3. The architecture landscape with respect to trainability (left), expressivity (middle), and generalization (right) on a 2D plane projected via PCA from the search space. The red star indicates the parent of a search by Reinforcement Learning, and two crosses represent two children spawned from the same parent (at "Early" or "Late" search stage), but searched with different randomness. The simple geometry of NAS-Bench-201 is easier to search, whereas the DARTS space is much more complex and hard to explore. [10], [64]: Reinforcement learning (RL) treats the NAS search process as a sequential decision making process. The policy agent formulates a single-path architecture by choosing a sequence of operators as actions, and uses the accuracy, loss value, or our training-free indicators of sampled architecture as the reward to update its internal policy distribution. Evolution [24]: Starting from a randomly initialized pool of architectures, the evolution keeps updating the population by mutating the high-ranked architectures. The ranking criteria could be the accuracy, loss value, or our trainingfree indicators of sampled architectures.

REINFORCE
Fast Probabilistic NAS: FP-NAS views search evaluations from an underlying distribution over architectures [65]. It constructs a supernet and corresponding architecture parameters. Leveraging Importance Weighted Monte-Carlo EB algorithm [68], architecture parameters are optimized to maximize the model likelihoods of sampled architectures, which are weighted by a proxy architecture performance indicator, like accuracy, loss value, or training-free indicators.

Implementation Details
In this section, we include more details regarding Algorithm 1 in terms of different search methods.

Reinforcement Learning
The policy agent maintains a internal state to represent the architecture search space, denoted as θ A . This internal state can be converted to a categorical distribution of the architectures (A) via softmax: A = σ(θ A ).
Stopping Criterion: We stop the RL search when the entropy of A stops decreasing (total iterations T = 500 in our work). We train the RL agent with a learning rate as η = 0.04 on NAS-Bench-201 and η = 0.07 on DARTS space. Search Performance from NAS-Bench-201. Test accuracy with mean and deviation are reported. "optimal" indicates the best test accuracy achievable in the space. The search time cost of our TEG-NAS is agnostic to the size of dataset (Section 4.2). For REINFORCE [64], Evolution [24], and FP-NAS [65], three search costs are listed for CIFAR-10/CIFAR-100/ImageNet-16-120.
r stands for reward, and b for an exponential moving average of reward for the purpose of variance reduction. For the baseline method, reward is taken from the proxy inference, i.e., the test accuracy by 1-epoch truncated training. For our TEG-NAS, reward is composited of three parts: r = r κ + r R + r MSE . Taking r κ (reward from trainability) as the example: κ max,t = max(κ 1 ,κ 2 , · · · ,κ t ) (17) κ min,t = min(κ 1 ,κ 2 , · · · ,κ t ) whereκ t is the evaluated trainability of the architecture sampled at step t. We calculate r R (expressivity) and r MSE (generalization) in the same way. Architecture Deriving: To derive the final searched network, the agent chooses the architecture that has the highest probability, i.e., a * = argmax a σ(θ A )(a).

Evolution
The evolution search is first initialized with a population of 256 architectures by random sampling. We choose the size of the population based on Figure A-1(a) from [24].
Stopping Criterion: We stop the Evolution search when the population diversity stops decreasing (1000 iterations in our work). Population diversity is calculated as the averaged pair-wise architecture difference in their operator types.
Architecture Sampling: Following Real et al. [24], in each iteration, the evolution search first randomly samples a subset of 64 architectures out of the population. We choose this sampling size based on Figure A-1(a) from [24]. Next, the best architecture (a t ) from this subset is selected. For the baseline method, the best architecture is the top1 ranked by the proxy inference, i.e., the test accuracy by 1-epoch truncated training. For our TEG-NAS, the best architecture is the top1 by the sum of three rankings by trainability, expressivity, and generalization: rank κ + rank R + rank MSE . Each rank is calculated by sorting architectures in this current subset.
Update: Following Real et al. [24], in each iteration the population is updated by adding a new architecture and popping out the oldest architecture (the one that stays in the population for the longest time). The new architecture is generated by mutating the sampled one mentioned above. We follow the same mutation strategy from Real et al. [24].
Architecture Deriving: To derive the final searched network, the best architecture from the population is selected, where the criterion is the same as we choose a t (see above "Architecture Sampling").

Fast Probabilistic NAS
The Fast Probabilistic NAS (FP-NAS) formulates the search space as a supernet and shares its parameters to its subnetworks. The original FP-NAS search performs alternative optimization between network parameters and the architecture parameters (denoted as θ A ). This architecture parameter can be converted to a categorical distribution of the architectures (A) via softmax: A = σ(θ A ).
Stopping Criterion: We stop the FP-NAS search when the entropy of A stops decreasing (total epochs T = 100 in our work). We update the architecture parameters with a learning rate as η = 0.1.
Architecture Sampling: In each step, the FP-NAS samples a subset A t of λH(Prob(a i |A)) architectures from A.
Here H denotes the distribution entropy and λ is a predefined scaling factor where we set it to 0.25.
log(Prob(a i |A)) · e ri |At| j=1 e rj (20) r stands for reward, calculated in the same way as we did for Reinforcement Learning (Section 5.2.1). Architecture Deriving: To derive the final searched network, the FP-NAS chooses the architecture that has the highest probability, i.e., a * = argmax a σ(θ A )(a).

Results on NAS-Bench-201
NAS-Bench-201 [23] provides a cell-based search space and the performance of all 15,625 networks it contains using a unified protocol. The network's accuracy is directly available by querying the database, benefiting towards the study of NAS methods without network evaluation. It contains five operator types: none (zero), skip connection, conv1×1, conv3×3 convolution, and average pooling 3 × 3. We refer to their paper for details of the space. For the baseline methods, the RL agent and Evolution use the test accuracy after 1-epoch training as the reward or ranking criteria. The FP-NAS uses alternative training between architecture parameters and supernet parameters with stochastic gradient descent. For all results we report, we run for four independent times with different random seeds, and report the mean and standard deviation in Table 2.
We can see that for all three NAS methods (REINFORCE, Evolution, FP-NAS), our TEG-NAS framework boosts the search performance while significantly reduce the search time cost. Although [1] costs reduced search time (sampled only 25 architectures), they suffer from much inferior search accuracy and significantly larger variance. Moreover, by adopting our unified framework, the accuracy of TE-NAS can be further improved.

Results on DARTS Search Space
Architecture Space The DARTS space contains eight operator types: none (zero), skip connection, separable convolution 3 × 3 and 5 × 5, dilated separable convolution 3 × 3 and 5 × 5, max pooling 3 × 3, average pooling 3 × 3. During the evaluation we stack 20 cells to compose the network and set the initial channel number as 36 [17], [18], [73]. We place the reduction cells at the 1/3 and 2/3 of the network. Each cell contains six nodes.
The architecture for ImageNet is slightly different: the network is stacked with 14 cells with the initial channel number set to 48. During retraining evaluation. The spatial resolution is downscaled from 224 × 224 to 28 × 28 with the first three convolution layers of stride 2.
Evaluation Protocols We follow previous NAS works [18], [73], [74] to evaluate architectures after search. On CIFAR-10, we train the searched network with cutout regularization of length 16, drop-path [69] with probability as 0.3, and an auxiliary tower of weight 0.4. On ImageNet, we also use label smoothing during training. On both CIFAR-10 and ImageNet, the network is optimized by an SGD optimizer with cosine annealing, with a learning rate initialized as 0.025 and 0.5, respectively. Results Table 3 and 4 summarize the performance on CIFAR-10 and ImageNet. On three different NAS methods and two datasets, our training-free framework can reduce the top1 error and further save the search time cost over 2.3×. FP-NAS equipped with our TEG framework can even achieve the best top1 error evaluated on ImageNet. All trainingfree versions of three NAS methods can now complete the search with less than a half GPU day. These search improvements on the large-scale DARTS space and datasets validate the effectiveness and efficiency of our unified TEG-NAS framework.

Searched Architecture on DARTS Search Space
We visualize the searched normal and reduction cells on DARTS space, by Reinforcement Learning (Figure 5), Evolution ( Figure 6), and FP-NAS (Figure 7)).

Ablation Study onκ,R, and MSE
To validate the necessity of considering all of the trainability, expressivity, and generalization, we conduct an ablation study in Table 5 using Reinforcement Learning on Cifar100 on NAS-Bench-201. As the baseline method, the RL agent uses the test accuracy after 1-epoch training as the reward.
We can see that the guidance from every single indicator outperforms the truncated training, with much less search time cost. Finally, we achieve the best search performance once equipped with allκ,R, and MSE.

CONCLUSION
We proposed a unified and explainable NAS framework that benefit both various popular search methods and search interpretation. We successfully disentangle the network's characteristics into three distinct aspects: Trainability, Expressivity, Generalization, or "TEG" for short, and leverage all of them to provide effective and efficient guidance for NAS search. Extensive studies on different NAS search methods validate the superior performance of our TEG-NAS framework. More importantly, we for the first time visualize the search trajectory on architecture landscapes from different search spaces, contributing to a better undertanding of both search and geometry of architecture space. We hope our work encourages the community to further explore NAS methods that benefit from extremely low cost, and provide a better understanding of the architectures and complexity of different search spaces.