Year: 2021

Abstract:
A key challenge in neural architecture search (NAS) is quickly inferring the predictive performance of a broad spectrum of networks to discover statistically accurate and computationally efficient ones. We refer to this task as model performance inference (MPI). The current practice for efficient MPI is gradient-based methods that leverage the gradients of a network at initialization to infer its performance. However, existing gradient-based methods rely only on heuristic metrics and lack the necessary theoretical foundations to consolidate their designs. We propose GradSign, an accurate, simple, and flexible metric for model performance inference with theoretical insights. The key idea behind GradSign is a quantity Ψ to analyze the optimization landscape of different networks at the granularity of individual training samples. Theoretically, we show that both the network’s training and true population losses are proportionally upper bounded by Ψ under reasonable assumptions. In addition, we design GradSign, an accurate and simple approximation of Ψ using the gradients of a network evaluated at a random initialization state. Evaluation on seven NAS benchmarks across three training datasets shows that GradSign generalizes well to real-world networks and consistently outperforms state-of-the-art gradient-based methods for MPI evaluated by Spearman’s ρ and Kendall’s Tau. Additionally, we integrate GradSign into four existing NAS algorithms and show that the GradSign-assisted NAS algorithms outperform their vanilla counterparts by improving the accuracies of best-discovered networks by up to 0.3%, 1.1%, and 1.0% on three real-world tasks.

text: A key challenge in neural architecture search (NAS) is quickly inferring the predictive performance of a broad spectrum of networks to discover statistically accurate and computationally efficient ones. We refer to this task as model performance inference (MPI). The current practice for efficient MPI is gradient-based methods that leverage the gradients of a network at initialization to infer its performance. However, existing gradient-based methods rely only on heuristic metrics and lack the necessary theoretical foundations to consolidate their designs. We propose GradSign, an accurate, simple, and flexible metric for model performance inference with theoretical insights. The key idea behind GradSign is a quantity Ψ to analyze the optimization landscape of different networks at the granularity of individual training samples. Theoretically, we show that both the network’s training and true population losses are proportionally upper bounded by Ψ under reasonable assumptions. In addition, we design GradSign, an accurate and simple approximation of Ψ using the gradients of a network evaluated at a random initialization state. Evaluation on seven NAS benchmarks across three training datasets shows that GradSign generalizes well to real-world networks and consistently outperforms state-of-the-art gradient-based methods for MPI evaluated by Spearman’s ρ and Kendall’s Tau. Additionally, we integrate GradSign into four existing NAS algorithms and show that the GradSign-assisted NAS algorithms outperform their vanilla counterparts by improving the accuracies of best-discovered networks by up to 0.3%, 1.1%, and 1.0% on three real-world tasks.

heading: 1 INTRODUCTION
text: As deep learning methods evolve, neural architectures have gotten progressively larger and more sophisticated (He et al., 2015; Ioffe & Szegedy, 2015; Krizhevsky et al., 2017; Devlin et al., 2019; Rumelhart et al., 1986; Srivastava et al., 2014; Kingma & Ba, 2017), making it increasingly challenging to design model architectures that can achieve state-of-the-art predictive performance manually. To alleviate this challenge, recent work has proposed several approaches to automatically discover statistically accurate and computationally efficient neural architectures. The most common approach is neural architecture search (NAS), which explores a comprehensive search space of potential network architectures based on compositions of basic network modules to discover architectures outperforming human-designed counterparts (Liu et al., 2018a; Zoph & Le, 2016; Pham et al., 2018).
A key challenge in existing automated approaches is quickly assessing the predictive performance of a diverse set of candidate architectures to discover performant ones. We refer to this task as model performance inference (MPI). A straightforward approach for MPI is directly training candidate architectures on a dataset until convergence and recording the achieved training losses and validation accuracies (Frankle & Carbin, 2018; Chen et al., 2020a; Liu et al., 2018a; Zoph & Le, 2016). Though accurate, this approach is computationally prohibitive and cannot scale to large networks or datasets.
The current practice to efficient MPI is gradient-based methods that leverage the gradient information of a network at initialization to infer its predictive performance (Lee et al., 2018; Wang et al., 2020; Tanaka et al., 2020). Compared to directly measuring the accuracy of candidate networks on a training dataset, gradient-based methods are computationally more efficient since they only require evaluating a mini-batch of gradients at initialization. However, existing gradient-based methods rely only on heuristic metrics and lack the necessary theoretical insights to consolidate their designs.
In this paper, we propose GradSign, a simple yet accurate metric for MPI with theoretical foundations. GradSign is inspired by analyzing the optimization landscapes of individual training samples. GradSign takes as inputs a mini-batch of sample-wise gradients evaluated at a random initialization point and outputs the statistical evidence of a network that highly correlates to its well-trained predictive performance measured by accuracy on the entire dataset.
Prior theoretical results (Allen-Zhu et al., 2019) show that for a sufficiently large neighborhood of a randomly initialized point, the optimization landscape is nearly convex and semi-smooth. To realize its potential for MPI, we generalize these results to sample-wise optimization landscapes and propose a quantity Ψ to measure the density of sample-wise local optima in the convex areas around a random initialization point. Additionally, we prove that both the training and population losses (i.e., generalization error) of a network are proportionally upper bounded by Ψ2 under reasonable assumptions.
Based on our theoretical results, we design GradSign, an accurate and simple approximation of Ψ, and empirically show that GradSign generalizes to realistic setups that may violate our assumptions. In addition, our method uses only the sample-wise gradient information at a random initialization point to provide statistical evidence to infer Ψ, which makes it efficient to compute and easy to implement.
Extensive evaluation on seven NAS benchmarks (i.e., NAS-Bench-101, NAS-Bench-201, and five design spaces of NDS) across three datasets (i.e., CIFAR-10, CIFAR-100, and ImageNet16-120) shows that GradSign consistently outperforms existing SOTA gradient-based methods in all circumstances. Furthermore, we integrate GradSign into existing NAS algorithms and show that the GradSign-assisted variants of these NAS algorithms lead to more accurate architectures.
Contributions. This paper makes the following contributions:
• We provide a new perspective to view the overall optimization landscape of a network as a combination of sample-wise optimization landscapes. Based on this insight, we introduce a new quantity Ψ that provides an upper bound on both a network’s training and population losses under reasonable assumptions.
• To infer Ψ, we propose GradSign, an accurate and simple estimation of Ψ. GradSign enables fast and efficient MPI using only the gradients of a network at initialization.
• We empirically show that our method could generalize reasonably well for modern network architectures by outperforming other SOTA gradient-based MPI methods. We additionally show that with the help of our method, SOTA NAS algorithms can be further improved.

heading: 2 RELATED WORK
text: Table 1 summarizes existing approaches to inferring the statistical performance of neural architectures.
Sample-based methods assess the performance of a neural architecture by training it on a dataset. Though accurate, sample-based methods require a surrogate training procedure to evaluate each architecture. EconNAS (Zhou et al., 2020) mitigates the cost of training candidate architectures by reducing the number of training epochs, input dataset sizes, resolution of input images, and model sizes.
Theory-based methods leverage recent advances in deep learning theory, such as Neural Tangent Kernel (Jacot et al., 2018) and Linear Region Analysis (Serra et al., 2018), to assess a model’s accuracy (Chen et al., 2020a; Mellor et al., 2021; Park et al., 2020). In particular, NNGP (Park et al., 2020) infers a model’s performance by fitting its kernel regression parameters on a training dataset and evaluating its accuracy on a validation set, which alleviates the burden of training. As another example, Chen et al. (2020a) utilizes the kernel condition number proposed in Xiao et al. (2020), which can be theoretically proved to correlate to training convergence rate and generalization performance. However, this theoretical evidence is only guaranteed for extremely wide networks while having a specialized initialization mode. While the linear region analysis used in Mellor et al. (2021), Lin et al. (2021) and Chen et al. (2020a) is easy to implement, such technique is only applicable to networks with ReLU activations (Agarap, 2018).
Learning-based methods train a separate network (e.g., graph neural networks) to predict a network’s accuracy (Liu et al., 2018a; Luo et al., 2020; Dai et al., 2019; Wen et al., 2020; Chen
et al., 2020b; Siems et al., 2020). Though these learned models can achieve high accuracies on a specific task, this approach requires constructing a training dataset with sampled architectures for each downstream task. As a result, existing learning-based methods are generally task-specific and computationally expensive.
Gradient-based methods infer the statistical performance of a network by leveraging the gradient information at initialization, which can be easily obtained using an automated differentiation tool in today’s ML frameworks, such as PyTorch (Paszke et al., 2017) and TensorFlow (Abadi et al., 2016). The weight-wise salience score computed by several pruning at initialization (Lee et al., 2018; Wang et al., 2020; Tanaka et al., 2020) methods can easily be adapted to MPI settings by summing scores up. Though lack of theoretical foundations, such migrations have been empirically proven to be effective as baselines in recent works (Abdelfattah et al., 2021a; Mellor et al., 2021; Lin et al., 2021). An alternative stream of work (Turner et al., 2019; 2021; Theis et al., 2018) uses approximated secondorder gradients, known as empirical Fisher Information Matrix (FIM), at a random initialization point to infer the performance of a network. Empirical FIM (Martens, 2014) is a valid approximation of a model’s predictive performance only if the model’s parameters are a Maximum Likelihood Estimation (MLE). However, this assumption is invalid at a random initialization point, making FIM-based algorithms inapplicable. The key difference between GradSign and existing gradient-based methods is that our method is based on a fine-grained analysis of sample-wise optimization landscapes rather than heuristic insights. In addition, GradSign also provides the first attempt for MPI by leveraging the optimization landscape properties contained in sample-wise gradient information, while prior gradient-based methods only focus on gradients evaluated in a full batch fashion.

heading: 2.1 NEURAL ARCHITECTURE SEARCH
text: Recent works (He et al., 2021; Cai et al., 2019; 2018; Tan & Le, 2019; Howard et al., 2019) have proposed several algorithms to explore a NAS search space and discover highly accurate networks. RS (Bergstra & Bengio, 2012) is one of the baseline algorithms that generates and evaluates architectures randomly in the search space. REINFORCE (Williams, 1992) moves a step forward by reframing NAS as a reinforcement learning task where accuracy is the reward and architecture generation is the policy action. Given limited computational resources, BOHB (Falkner et al., 2018) uses Bayesian Optimization (BO) to propose candidates while uses HyperBand(HB) (Li et al., 2017) for searching resource allocation. REA (Real et al., 2019) uses a simple yet effective evolutionary searching strategy that achieves state-of-the-art performance. GradSign is complementary to and can be combined with existing NAS algorithms. We integrate GradSign into the NAS algorithms mentioned above and show that GradSign can improve the search procedure of NAS algorithms on various real-world tasks.

heading: 2.2 OPTIMIZATION LANDSCAPE ANALYSIS
text: Inspired by the fact that over-parameterized networks always find a remarkable fit for a training dataset (Zhang et al., 2016), optimization landscape analysis has been one of the main focuses in deep learning theory (Brutzkus & Globerson, 2017; Du et al., 2018; Ge et al., 2017; Li & Yuan, 2017; Soltanolkotabi, 2017; Allen-Zhu et al., 2019). Even though existing theoretical results for optimization landscape analysis rely on strict assumptions on the landscape’s smoothness, convexity, and initialization point, we can leverage theoretical insights to guide the design of GradSign. In
θ*
θ*1
l( fθ(x1), y1)
θ*2
l( fθ(x2), y2)
|θ*1 − θ*2 |
θ
l
(a) Optimization landscape with sparser sample-wise local optima corresponding to worse J(θ∗).
θ
l
θ* θ*1
l( fθ(x1), y1)
θ*2
l( fθ(x2), y2)
|θ*1 − θ*2 |
(b) Optimization landscape with denser sample-wise local optima corresponding to better J(θ∗).
Figure 1: Illustration of our theoretical insight that denser sample-wise local optima indicate lower training losses. As the distances (|θ∗1 − θ∗2 |, shown in red) between the local optima across samples reduce, there is a higher probability that the gradients of different samples have the same sign at a random initialization point, shown as the green areas.
addition, SGD-based optimizers trained from randomly initialized states hardly encounter nonsmoothness or non-convexity in practice for varieties of architectures (Goodfellow et al., 2014). Furthermore, Allen-Zhu et al. (2019) provides theoretical evidence that for a sufficiently large neighborhood of a randomly initialized point, the optimization landscape is nearly convex and semismooth. Different from existing optimization landscape analyses depending on objectives evaluated across a mini-batch of training samples, we propose a new perspective that decomposes a mini-batch objective into the aggregation of sample-wise optimization landscapes. To the best of our knowledge, our work is the first attempt to inferring models’ performance by leveraging sample-wise optimization landscapes.

heading: 3 THEORETICAL FOUNDATIONS

heading: 3.1 INSIGHTS
text: Conventional optimization landscape analyses focus on objectives across a mini-batch of training samples and miss potential evidence hidden in the optimization landscapes of individual samples. By decomposing a mini-batch objective into the summation of sample-wise objectives across individual samples in a mini-batch, we can distinguish better local optima as illustrated in Figure 1. Both Figure 1a and Figure 1b reach a local optimum at θ∗ for the mini-batch objective J = 12 (l(fθ∗(x1), y1)+ l(fθ∗(x2), y2)). However, the optimization landscape in Figure 1b contains a better local optimum θ∗ (i.e., a lower J). This can be distinguished by analyzing the relative distance between local optima across training samples (i.e., |θ∗1 − θ∗2 | in Figure 1). For a mini-batch with more than two samples, we use a sample-wise local optima density measurement Ψ defined in Section 3.2 to represent the overall closeness of sample-wise local optima. Intuitively, as the distances between the local optima across samples reduce (shown as the red areas in Figure 1), there is a higher probability that the gradients of different samples evaluated at a random initialization point have the same sign (shown as the green areas in Figure 1). Driven by this insight, we propose GradSign to infer the sample-wise local optima density Ψ statistically. The design of GradSign is based on our theoretical results that a network with denser sample-wise local optima has lower training and generalization losses under reasonable assumptions. We introduce the notations and assumptions in Section 3.2, provide a formal derivation of our theoretical results in Section 3.3, and present GradSign in Section 4.

heading: 3.2 PRELIMINARIES
text: We use S = {(xi, yi)}i∈[n] to denote training samples, where each xi ∈ Rd is a feature vector, and yi is the corresponding label. We use l(ŷi, yi) to represent a loss function where ŷi is the prediction of our model. We use fθ(·) : Rd → Ro to denote the model parameterized by θ and use θ0 ∈ Rm to denote random initialized parameters where m is the number of model parameters. Bold font constant denote a constant vector such as 0 = [0, 0, · · · , 0] whose dimension depends on the corresponding situation. D denotes the underline data distribution, which is the same for training and testing.
Our theoretical results rely on the assumption that there exists a neighborhood Γθ0 for a random initialization point θ0 in which sample-wise optimization landscapes are almost convex and semismooth. Note that our assumption is weaker than the ones stated in prior work (Allen-Zhu et al., 2019). We use {θ∗i }i∈[n] ∈ Γθ0 to denote a local optima in the convex areas attached to the i-th sample near the initialization point θ0. Under this assumption, the overall optimization landscape is also convex and semi-smooth within the neighborhood Γθ0 as additive operations preserve both. We use θ∗ to denote a local optimum within Γθ0 for the mini-batch optimization landscape. Note that θ∗ always lie in the convex hull of {θ∗i }i∈[n]. Additionally, we assume that only gradient-based optimizers 1 are used during training. Thus the optimizer eventually converges to θ∗.
Finally, our theoretical analysis assumes that every Hessian in the set {∇2l(fθ(xi), yi)|∀i ∈ [n], θ ∈ Γθ0} is almost diagonal as in the Neural Tangent Kernel (NTK) regime (Jacot et al., 2018). Section 5 shows that our method generalizes well to real-world networks that may violate this assumption.
Sample-wise local optima density. We use sample-wise local optima density to represent the relative closeness of {θ∗i }i∈[n]. Given a dataset S = {(xi, yi)}i∈[n], an objective function l(ŷi, yi), and a model class fθ(·), we use ΨS,l(fθ0(·)) to measure the average distance between the local optima across samples {θ∗i }i∈[n] near a random initialization point θ0:
ΨS,l(fθ0(·)) = √ H n2 ∑ i,j ‖θ∗i − θ∗j ‖1 (1)
H ∈ R is a smoothness upper bound: ∀k ∈ [m], i ∈ [n], [∇2l(fθ(xi), yi)]k,k ≤ H. This upper bound always exists due to the smoothness assumption. Intuitively, ΨS,l(fθ0(·)) can be interpreted as the mean Manhattan distance with respect to each pair of {θ∗i }i∈[n] normalized by the inverse of the square root of the smoothness upper bound. The denser {θ∗i }i∈[n] are, the smaller ΨS,l(fθ0(·)) is. In an ideal case, ΨS,l(fθ0(·)) = 0 when all local optima are located at the same point.

heading: 3.3 MAIN RESULTS
text: We show the local optimum property of sample-wise optimization landscapes in the following lemma.
Lemma 1 There exists no saddle point in a sample-wise optimization landscape and every local optimum is a global optimum.
Using Lemma 1, we can draw a relation between the training error J = 1n ∑ i l(fθ(xi), yi) and ΨS,l(fθ0(·)) using the following theorem.
Theorem 2 The training error of a network on a dataset J = 1n ∑ i l(fθ(xi), yi) is upper bounded by n 3
2 Ψ 2 S,l(fθ0(·)), and the bound is tight when ΨS,l(fθ0(·)) = 0.
Finally, we show that ΨS,l(fθ0(·)) also provides an upper bound for the generalization performance of a network measured by population loss.
Theorem 3 Given that Var(xu,yu)∼D[‖θ∗ − θ∗u‖21] is bounded by σ2 where θ∗u is a local optimum attached to the convex area near θ0 for l(fθ(xu), yu). With probability 1 − δ, the true population loss is upper bounded by n 3
2 Ψ 2 S,l(fθ0(·)) + σ√nδ .
A formal proof of all theoretical results is available in Appendix A.1.
Main takeaways: The key takeaway of our theoretical results is that ΨS,l(fθ0(·)) closely relates to an upper bound for the training and generalization performance of a network. Albeit theoretically sound, ΨSl(fθ0(·)) is intractable to be directly measured. Instead, we derive a simple yet accurate metric to reflect ΨS,l(fθ0(·)), which we present in the next section.

heading: 4 GRADSIGN
text: Inspired by the theoretical results derived above, we introduce GradSign, a simple yet accurate metric for model performance inference. The key idea behind GradSign is a simple and neat quantity to
1Gradient descent with infinitesimal step size
statistically reflect the relative value of ΨS,l(fθ0(·)). Specifically, ΨS,l(fθ0(·)) ∝ C − ∑ k ∑ i,j P (sign([∇θl(fθ(xi), yi)|θ0 ]k) = sign([∇θl(fθ(xj), yj)|θ0 ]k)) (2)
where C is a constant and k is the vector index. Detailed derivation is given in Appendix A.1. Using the above relation, we can infer ΨS,l(fθ0(·)) by directly measuring the signs of the gradients for a mini-batch of training samples at a randomly initialized point instead of going through an end-to-end training process.
To enable more efficient calculation of ΨS,l(fθ0(·)), we make a further simplification and use the following sample observation: ∑
k | ∑ i sign([∇θl(fθ(xi), yi)|θ0 ]k)| (3)
to infer the true probability ∑ k ∑ i,j P (sign([∇θl(fθ(xi), yi)|θ0 ]k) = sign([∇θl(fθ(xj), yj)|θ0 ]k)) whose relation is given by:
1
n2 ∑ i,j 1sign([∇θl(fθ(xi),yi)|θ0 ]k)=sign([∇θl(fθ(xj),yj)|θ0 ]k) (4)
∝ | ∑ i sign([∇θl(fθ(xi), yi)|θ0 ]k)|2 (5)
The proof of this simplification is included in Appendix A.1. Given the above relationship, we formally state our algorithm pipeline as Algorithm 1. Note that a higher GradSign score indicates better model performance as we have an inverse correlation in Equation (2).
Algorithm 1: GradSign Result: GradSign score τf for a function class fθ Given S = {(xi, yi)}i∈[n], randomly select initialization point θ0; Initialize g[n,m]; for i = 1, 2, · · · , n do
for k = 1, 2, · · · ,m do g[i, k] = sign([∇θl(fθ(xi), yi)|θ0 ]k)
end end τf = ∑ k | ∑ i g[i, k]|; return τf

heading: 5 EXPERIMENTS
text: In this section, we empirically verify the effectiveness of our metric against SOTA gradient-based methods on three neural architecture search (NAS) benchmarks, including NAS-Bench-101 (Ying et al., 2019), NAS-Bench-201 (Dong & Yang, 2020) and NDS (Radosavovic et al., 2019)2. Theorybased, sample-based, and learning-based methods are excluded in our evaluation, as they either require further training processes or have strong assumptions not suitable for generic architectures.
Baselines. We compare GradSign against existing gradient-based methods, including snip (Lee et al., 2018), grasp (Wang et al., 2020), fisher (Turner et al., 2019), and Synflow. In addition, we also include grad_norm as a heuristic method and a one-shot SOTA MPI metric NASWOT(Mellor et al., 2021). Since all gradient-based methods share a similar calculation pipeline (i.e., evaluating the gradients of a mini-batch at a random initialization point), we set the initialization mode and batch size to be the same across all methods to guarantee fairness. Experimental setup details are included in Appendix A.2. To align with the experimental setup of prior work (Abdelfattah et al., 2021b; Mellor et al., 2021), we use two criteria to evaluate the correlations between different metrics and test accuracies across approximately 20k networks:
Spearman’s ρ (Daniel et al., 1990) characterizes the monotonic relationships between two variables. The correlation score is restricted in range [-1, 1], where ρ = 1 denotes a perfect positive monotonic
2All datasets have consented for research purposes and no identifiable personal information is included.
relationship and ρ = −1 denotes a perfect negative monotonic relationship. Following prior work, we use Spearman’s ρ to evaluate gradient-based methods on NAS-Bench-101 and NAS-Bench-201.
Kendall’s Tau. Similar to Spearman’s ρ as a correlation measurement, Kendall’s Tau is also restricted between [-1, 1]. While Spearman’s ρ is more sensitive to error and discrepancies, Kendall’s Tau is more robust with a smaller gross error sensitivity. We use Kendall’s Tau to quantify the correlation between SOTA one-shot metric scores and model testing accuracies over the NDS search space.

heading: 5.1 NAS-BENCH-101
text: NAS-Bench-101 is the first dataset targeting large-scale neural architecture space, containing 423k unique convolutional architectures trained on the CIFAR-10 dataset. The benchmark provides the test accuracy of each architecture in the search space, which we use to calculate the corresponding Spearman’s ρ. We use a randomly sampled subset (≈ 4500) of the whole architecture space and a batch size of 64 in this experiment. Table 2 summarizes the results. GradSign significantly outperforms existing gradient-based methods and heuristic approaches and improves the Spearman’s ρ score by 25% compared to the best existing method (0.363→ 0.449).

heading: 5.2 NAS-BENCH-201
text: NAS-Bench-201 is an extended version of NAS-Bench-101 with a different search space, containing 15,625 cell-based candidate architectures evaluated across three datasets: CIFAR-10, CIFAR-100 and ImageNet 16-120. The benchmark provides the test accuracies on the three datasets for all candidate architectures in the search space. We evaluate Spearman’s ρ scores for GradSign and existing gradient-based methods. The experiments are conducted overall 15,265 architectures in NAS-Bench-201. The batch size is set to 64. The results on the three datasets are summarized in Table 3. GradSign consistently achieves the best performance across all three datasets and improves the Spearman’s ρ scores by ≈ 4% over the best existing approaches. This improvement is significant as the more Spearman’s ρ approaches 1, the more difficult it can be further improved.
We further select 1000 architecture candidates randomly in the NAS-Bench-201 search space and visualize their testing accuracies and GradSign scores in Figure 2.
Figure 2 shows a highly positive correlation between the GradSign score and actual test accuracy of 1000 architectures. A higher GradSign score indicates higher confidence for the statistical performance of architecture. Note that the GradSign scores show a clustering pattern, which may correspond to different architecture classes in the NAS-Bench-201 search space.

heading: 5.3 NAS DESIGN SPACE (NDS)
text: NDS is a unified searching framework that includes five different design spaces: NAS-Net (Zoph et al., 2018), AmoebaNet (Real et al., 2019), PNAS (Liu et al., 2018a), ENAS (Pham et al., 2018), DARTS (Liu et al., 2018b). Each space contains∼ 1k networks that are fully trained on the CIFAR-10 dataset. We include the performance of our method along with grad_norm, Synflow, and NASWOT on all five design spaces evaluated by Kendall’s Tau and show the results in Table 4. GradSign significantly and consistently outperforms all other MPI methods in all five design spaces.

heading: 5.4 ARCHITECTURE SELECTION
text: We evaluate whether GradSign can be directly used to select highly accurate architectures in a NAS search space. To pick a top architecture, we randomly sample N candidates in a NAS search space, choose the one with the highest GradSign score, and measure its validation/test accuracies (mean±std). We compare GradSign with Synflow, NASWOT, Random, and Optimal. Random uniformly samples architectures in the search space, while Optimal always chooses the best architecture across N candidates. The results3 are summarized in Table 5. N in parenthesis indicates the number of architectures sampled in each run. All methods can generally find more accurate architectures with a high N . In addition to outperforming Synflow and NASWOT, GradSign (N = 100) can also find better networks even compared to NASWOT(N = 1000). The results show that GradSign can directly identify accurate architectures besides highly correlating to networks’ test accuracies.

heading: 5.5 GRADSIGN-ASSISTED NEURAL ARCHITECTURE SEARCH
text: Besides evaluating GradSign on the Spearman’s ρ and Kendall’s Tau scores as prior work, we also integrate GradSign into various neural architecture search algorithms and evaluate how GradSign can assist neural architecture search on real-world tasks. Specifically, we integrate GradSign into four NAS algorithms: REA, REINFORCE, BOHB and RS. We design a corresponding method for each NAS algorithm that uses the GradSign scores of candidate architectures to guide the search.
3the results for NASWOT are referenced from their paper
Specifically, we integrate GradSign into each NAS algorithm by replacing the random selection of architectures with GradSign-assisted selection. We name these GradSign-assisted variants G-REA, G-REINFROCE, G-HB, and G-RS, and describe their algorithm details in Appendix A.
To evaluate how GradSign can improve the search procedure of NAS algorithms, we run each algorithm with and without GradSign’s assistance for 500 runs on NAS-Bench-201 and report the validation and test accuracies of the best-discovered architecture in each run. Following prior work (Mellor et al., 2021; Dong & Yang, 2020), all searches are conducted on the CIFAR-10 dataset with a time budget of 12000s while the performance is evaluated on CIFAR-10, CIFAR-100 and ImageNet16-120. The baselines also include A-REA (Mellor et al., 2021), a variant of REA that uses the NASWOT scores at the initial population selection phase.
Table 6 shows the results. The GradSign-assisted NAS algorithms outperform their counterparts by improving test accuracy by up to 0.3%, 1.1%, and 1.0% on the three datasets.

heading: 6 CONCLUSION
text: In this paper, we propose a model performance inference metric GradSign and provide theoretical foundations to support our metric. Instead of focusing on full batch optimization landscape analysis, we move a step further to sample-wise optimization landscape properties, which give us additional information to uncover the quality of the local optima encountered on the optimization trajectory. We propose ΨS,l(fθ0(·)) to quantitatively characterize the potential of a model fθ(·) at a random initialization point θ0 based on our theory results. Finally, we design the GradSign metric to statistically infer the value of ΨS,l(fθ0(·)) to give out our final score for model performance inference. Empirically, we have demonstrated that our method consistently achieves the best correlation with true model performance among all other SOTA gradient-based metrics. In addition, we also verified the practical value of our method in assisting existed NAS algorithms to achieve better results. Given that our metric is generic and promising, we believe that our work not only assists in accelerating MPI-related applications but sheds some light on optimization landscape analysis as well. Meanwhile, the effectiveness of our method may further reduce the energy cost introduced by modern NAS algorithms.

heading: A APPENDIX
text: A.1 PROOF
Lemma 1 Proof: For a single training sample (xi, yi), we minimize its objective function l(fθ(xi), yi) with gradient descent:
∇θl(fθ(xi), yi) = ∂l(fθ(xi), yi)
∂fθ(xi) · f ′θ(xi) (6)
At any local optimal point θ∗i , we have ∇θl(fθ(xi), yi)|θ∗i = 0, but f ′ θ(xi) 6= 0 for conventional neural architectures with at least one dense layer 4. Therefore, we show ∂l(fθ(xi),yi)∂fθ(xi) |θ∗i must be equal to 0. For the commonly used objective functions, such as Mean Squared Error Loss and Cross Entropy Loss, this derivative is equal to C(fθ(xi)− yi), where C is a non-zero constant. Hence we have fθ∗i (xi) = yi and l(fθ∗i (xi), yi) = 0 at local optima θ ∗ i , which makes θ ∗ i also a global optima as it is impossible to obtain a lower loss value for this single sample. In addition, at local optima θ∗i , we have:
∇2θl(fθ(xi), yi) = ∇θ( ∂l(fθ(xi), yi)
∂fθ(xi) · f ′θ(xi)) (7)
= ∂2l(fθ(xi), yi)
∂fθ(xi)2 · f ′θ(xi)f ′θ(xi)> +
∂l(fθ(xi), yi)
∂fθ(xi) · f ′′θ (xi) (8)
= C · f ′θ(xi)f ′θ(xi)> (9) The above equation implies that∇2θl(fθ(xi), yi) is a positive semi-definite matrix, since C > 0. This concludes the proof of non existence of saddle points in a sample-wise optimization landscape. This result aligns with our convexity assumptions in Section 3.2.
Theorem 2 Proof: Recall that θ∗ denotes a local optima of J which could be reached by a gradientflow based optimizer start from θ0. Since θ0 is randomly sampled and [∇2l(fθ(xi), yi)]k,k ≤ H, we have:
J = 1
n ∑ i l(fθ∗(xi), yi) (10)
≤ 1 n ∑ i H · ‖θ∗ − θ∗i ‖22 (11) ≤ H n ∑ i ‖θ∗ − θ∗i ‖21 (12) ≤ H n ∑ i,j ‖θ∗i − θ∗j ‖21 (13)
≤ n3Ψ2S,l(fθ0(·)) (14)
where Eq 10→ Eq 11 uses the basic property of the smoothness upper bound H and the fact that each local optimum θ∗i satisfies l(fθ∗i (xi), yi) = 0. Eq 11→ Eq 12 uses Jensen Inequality for square root operators. Eq 12→ Eq 13 is derived from the fact that for each dimension in (θ∗ − θ∗i ) we have:
|[θ∗ − θ∗i ]k| ≤ ∑ j |[θ∗j − θ∗i ]k| (15)
Otherwise, θ∗ dose not lie in the convex hull of {θ∗i }i∈[n] which contradicts with our assumption stated in Section 3.2. The bound is tight when θ∗i = θ ∗ j ,∀i, j ∈ [n].
Eq 10→Eq 11: As we have ∇2l(fθ(xi), yi) HI and l(fθ∗i (xi), yi) = 0,∇θl(fθ(xi), yi)|θ∗i = 0, we could derive the following inequality:
l(fθ∗(xi), yi) ≤ l(fθ∗i (xi), yi) +∇θl(fθ∗i (xi), yi) >(θ∗ − θ∗i ) + H 2 ‖θ∗ − θ∗i ‖22 (16)
= H 2 ‖θ∗ − θ∗i ‖22 (17)
4The gradient values corresponding to the bias term of the last dense layer are always non-zero.
we thus have 1n ∑ i l(fθ∗(xi), yi) ≤ 1 2n ∑ iH · ‖θ∗ − θ∗i ‖22.
Theorem 3 Proof: Let E(xu,yu)∼D[l(f∗θ (xu), yu)] denotes the true population error. With probability 1− δ, we have:
E(xu,yu)∼D[l(f ∗ θ (xu), yu)] ≤ HE(xu,yu)∼D[‖θ ∗ − θ∗u‖21] (18)
≤ H n n∑ i=1 ‖θ∗ − θ∗i ‖21 + σ√ nδ
(19)
≤ n3Ψ2S,l(fθ0(·)) + σ√ nδ
(20)
where n and σ are constants, S is a training dataset, and D denotes its underlying data distribution. This implies that ΨS,l(fθ0(·)) is an accurate indicator for the true population loss. Eq 18→ Eq 19 uses Chebyshev’s inequality, while Eq 19→ Eq 20 uses the same inequality derived in Claim 2. Algorithm Proof: Given that sample-wise local optima {[θ∗i ], i ∈ [n]} are contained in the convex area around θ0. We derive the following property:
sign([θ∗i − θ0]k) = sign([∇θl(fθ(xi), yi)|θ0 ]k) (21)
Since θ0 is a randomly chosen initialization point, without loss of generality, we assume θ0 is sampled from a hypercube [−a, a]. Thus we have:
P (sign([∇θl(fθ(xi), yi)|θ0 ]k) 6= sign([∇θl(fθ(xj), yj)|θ0 ]k)) = |[θ∗i ]k − [θ∗j ]k|
2a (22)
Where P (sign([∇θl(fθ(xi), yi)|θ0 ]k) 6= sign([∇θl(fθ(xj), yj)|θ0 ]k)) denotes the probability for [∇θl(fθ(xi), yi)|θ0 ]k and [∇θl(fθ(xj), yj)|θ0 ]k having different signs. Notice that we have completely dropped the dependency for θ∗i at this point and can simply infer from sign([∇θl(fθ(xi), yi)|θ0 ]k). To complete our proof:
ΨS,l(fθ0(·)) = √ H n ∑ i,j ‖θ∗i − θ∗j ‖1 (23)
= 2a √ H
n ∑ k ∑ i,j P (sign([∇θl(fθ(xi), yi)|θ0 ]k) 6= sign([∇θl(fθ(xj), yj)|θ0 ]k))(24)
∝ n2 − ∑ k ∑ i,j P (sign([∇θl(fθ(xi), yi)|θ0 ]k) = sign([∇θl(fθ(xj), yj)|θ0 ]k))(25)
Simplification Proof:: for each i, j and a given k, we could estimate P (sign([∇θl(fθ(xi), yi)|θ0 ]k) = sign([∇θl(fθ(xj), yj)|θ0 ]k)) using:
|sign([∇θl(fθ(xi), yi)|θ0 ]k) + sign([∇θl(fθ(xj), yj)|θ0 ]k)| 2
(26)
which is valid (not equal to zero) only when sign([∇θl(fθ(xi), yi)|θ0 ]k) == sign([∇θl(fθ(xj), yj)|θ0 ]k). Suppose we have p positive and n-p negative sign([∇θl(fθ(xi), yi)|θ0 ]k) for n samples, since we only care about samples share the same sign, the original probability estimation is (n−p) 2+p2
n2 = 1 2 + (n−2p)2 2n2 . Thus we only need to measure the quantity |n− 2p| which simply equals to | ∑ i sign([∇θl(fθ(xi), yi)|θ0 ]k)|.
A.2 EXPERIMENTS SETUP
The code we used during experimentation was mainly based on existed code base Abdelfattah et al. (2021b); Mellor et al. (2021)Abdelfattah et al. (2021b) which is under Apache-2.0 License.
The hardwares we used were Amazon EC2 C5 instances with no GPU involved and p3 instance with one V100 Tensor Core GPU.
As our methods is gradient-based which is training free, we don’t need to split our dataset. For Spearman’s correlation measurement on NAS-Bench-201, we set batch size to 64, which is used by most baselines. For the Kendall’s Tau experiment, other accuracy comparison experience and the GradSign assisted algorithms, we used a batch size of 128, also to match the batch size in other baselines (NASWOT). We use Pytorch default parameter initialization for all architectures. Random seed in correlation experiments is set to 42 which is also randomly chosen. For accuracy experiments, our results are summarized over 500 runs whose random seed are chosen randomly for each run. For the correlation evaluation of each individual architecture, we only use one θ0 for minimizing computational cost. Our approach can be easily generalized to an average of multiple θ0s and can trade-off between efficiency and accuracy.
A.3 ADDITIONAL RESULTS
Sample-based: Fig 3 compares EconNAS, a sample-based method, with existing gradient-based methods on MPI. Results of EconNAS are referenced from Abdelfattah et al. (2021b). To achieve a similar MPI performance as GradSign, EconNAS needs 500 minibatches of samples for each candidate’s proxy training, while all gradient-based methods (including GradSign) require only one minibatch. By increasing the number of minibatches, EconNAS can achieve higher Spearman’s ρ scores, which eventually converge to 0.85. At that point overfitting takes place and the score cannot be further improved.
Learning-based: Table 7 compares GradSign and existing learning-based methods (MLP, LSTM, and GATES) on the Kendall’s Tau correlation score. The results are referenced from Ning et al. (2020). For MLP and LSTM (Wang et al., 2019), the predictor uses Multi Layer Perceptron (MLP)
and Long Short Term Memory (LSTM) as the base predictor, while GATES (Ning et al., 2020) uses Graph Neural Network (GNN) as the base predictor. All results are obtained on NAS-Bench-201 and the GradSign’s score is averaged over all three datasets (CIFAR-10, CIFAR-100 and ImageNet16-120) as (Ning et al., 2020) does not indicate which dataset is used for calculating Kendall’s Tau.
To achieve a similar score as GradSign, MLP, LSTM and GATES-1 require an average of 1959, 978 and 1959 minibatches per sample respectively to prepare the dataset for training the predictors. Although GATES-2 achieves a better correlation score than GradSign, it still needs 195 minibatches per sample to prepare the dataset for training the GATES-2 predictor. In addition to the cost of preparing a training dataset, each predictor also has to be trained on the dataset as well, which involves 200 more epochs while the cost of evaluating GradSign is one mini-batch. With less minibatches evaluated for learning-based methods, their training set sizes shrink significantly (e.g., 195 mini-batches equal to 78 training samples and 7813 testing samples). This may result in overfitting to the training set.
We also includes the evaluation of GradSign for both MPI correlation performance and GradSignassisted NAS algorithms on the latest version of NAS-Bench-201 (NATS-Bench) across three datasets (CIFAR-10, CIFAR-100 and ImageNet16-120) in Table 8, Table 9. Results show GradSign is robust against hyper-parameter tuning as long as the trained networks can converge to near optimal. Also notice that GradSign-assisted NAS algorithms could not only achieve a better accuracy but lower variance as well compared to their non-assisted counterparts.
G-RS 91.23±0.22 94.02±0.22 72.12±0.82 72.15±0.78 45.43±0.74 45.83±0.80 REINFORCE 90.92±0.38 93.71±0.37 71.04±1.02 71.17±1.12 44.56±0.97 44.80±1.18 G-REINFORCE 91.20±0.23 93.98±0.23 71.93±0.91 72.05±0.89 45.28±0.77 45.64±0.86
To demonstrate the potential for GradSign in a more complicated computer vision task, we compare the performance of GradSign with ZenNAS following their setups and search space. Due to the limitation of computational resources, we only run 1000 evolution iterations using solely Zen score or GradSign score to select the architecture candidate and 20 epochs to train the selected architecture. Following ZenNAS’s setup, EfficientNet-B3 is used as teacher network when training selected architectures. The difference of two methods’ performance is nearly negligible considering the influence of random seeds and the Knowledge Distillation process. As we mentioned before, ZenNAS uses linear region analysis which makes it less flexible for arbitrary activation functions. On the other hand, since ZenNAS calculates an architecture complexity related score which is both dataset independent and initialization independent, it can be too general and results in low Spearman’s ρ as shown in Table 3.
In addition to computer vision tasks, we also evaluated GradSign on NAS-Bench-NLP against Synflow and grad_norm in Table 10. We observe that even though GradSign still achieves the best correlation score in this NLP task compared to baselines, its correlation score has dropped significantly compared to CV tasks.
A.4 GRADSIGN ASSISTED NAS ALGORITHMS
Algorithm 2: G-REA Result: Find the best performing architecture given the time constraint for 12000s Population = []; History = []; population_size; sample_size; pool_size; for 1, 2, · · · ,population_size do
model = random.arch(); model.acc, model.time_cost = eval(model); Population.append(model); History.append(model);
end while not exceeding time budget do
Sample = []; for 1, 2, · · · ,sample_size do
Sample.append(random.choice(Population)) end parent = max_acc(Sample); GradSign_pool = []; for 1, 2, · · · ,pool_size do /* GradSign assisted part */
model = mutate_arch(parent); model.score = GradSign(model); GradSign_pool.append(model);
end child = max_score(GradSign_pool); Population.append(child); History.append(child); Population.popleft();
end return max_acc(History)
Algorithm 3: G-RS Result: Find the best performing architecture given the time constraint for 12000s History = []; pool_size; while not exceeding time budget do
GradSign_pool = []; for 1, 2, · · · ,pool_size do /* GradSign assisted part */
model = random_arch(); model.score = GradSign(model); GradSign_pool.append(model);
end arch = max_score(GradSign_pool) arch.acc = eval(arch) History.append(arch);
end return max_acc(History);
Algorithm 4: G-REINFORCE Result: Find the best performing architecture given the time constraint for 12000s History = []; pool_size; policy πθ0 ; Reward = []; baseline; while not exceeding time budget do
arch = generate_arch(πθi ); GradSign_pool = []; for 1, 2, · · · ,pool_size do /* GradSign assisted part */
child = mutate_arch(arch); child.score = GradSign(child); GradSign_pool.append(child);
end arch = max_score(GradSign_pool); arch.acc = eval(arch); r= arch.acc; History.append(arch); Reward.append(r); baseline.update(r); θi+1 = θi +∇θEπθi [r − baseline]
end return max_acc(History); return
Algorithm 5: G-HB Result: Find the best performing architecture given the time constraint for 12000s Input: budgets bmin and bmax, η; smax = blogη bmaxbmin c; score_list = []; pool_size; for s ∈ {smax, smax−1, · · · , 0} do
config_space = []; set n = d smax+1s+1 · η
se; while sizeof(config_space) < n do
GradSign_pool = []; for 1, 2, · · · ,pool_size do /* GradSign assisted part */
model = random_arch(); if model in score_list then
model.score = score_list[model]; else
model.score = GradSign(model); score_list[model] = model.score;
end GradSign_pool.append(model);
end arch = max_score(GradSign_pool); config_space.append(arch);
end run SH on them with initial budget as ηs · bmax;
end return best evaluated architecture;

Review summaries:
Model performance inference is a key challenge in neural architecture search. This paper introduces GradSign, an accurate, simple, and flexible metric for model performance inference. GradSign approximately analyzes the optimization landscape of different networks at the granularity of individual training samples using the gradients evaluated at a random initialization state. Experimental results show that GradSign can generalize well to real-world networks and outperform state-of-the-art gradient-based methods for model performance inference.

This work discusses the problem of neural architecture search. While existing gradient methods are based on heuristics, this work proposes a metric called Gradsign for model performance inference, which provides some theoretical guarantees and performs well in practise.   Authors compare gradsign to a number of state of the art methods using 3 benchmarks involving CIFAR10, CIFAR100, and ImageNet16-120 datasets. Gradsign shows better performance compared to these methods.