GradSign: Model Performance Inference with Theoretical Insights
Authors: Zhihao Zhang
Zhihao Jia
Venue: ICLR 2022 Poster (2022)
Keywords: Model Performance Inference
Optimization Landscape
NAS

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 sample-wise optimization landscape of different networks. Theoretically, we show that  Ψ is an upper bound for both the training and true population losses of a neural network under reasonable assumptions. However, it is computationally prohibitive to directly calculate Ψ for modern neural networks. To
address this challenge, 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. Code is available at https://github.com/JackFram/GradSign

Published as a conference paper at ICLR 2022
GRADSIGN: MODEL PERFORMANCE INFERENCE WITH THEORETICAL INSIGHTS
Zhihao Zhang
Zhihao Jia
Cameggi Mellon University zh i haoz cs cmu. edu
Carnegie Mellon University zh hace cmu. edu
ABSTRACT
A key challenge in neural architecture search (NAS) is quickly inferring the predic- tive performance of broad spectrum of neural networks to discover statistically accurate and computationally efficient ones. We refer to this task as model perfor- mance inference (MPI). The current practice for efficient MPI is gradient-based methods that leverage the gradients of a network at initialization to infer its perfor- mance. However, existing gradient- grasient-based methods rely only 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. A key idea behind GradSign is a quantity Vr to analyze the sample-wise optimization landscape of different networks. Theoreti- cally, we show that V is an upper bound for both the training and true population losses of neural network under reasonable assumptions. However, com- putationally prohibitive to directly calculate V for modern neural networks. To address this challenge, we design GradSign, an accurate and simple approximation of Y using the gradients of network evaluated Evaluation on seven NAS benchmarks across three training datasets shows that GradSign generalizes well real-world neural networks and consistently outper- forms state-of- of- the art gradient- baadee methods for MPI evaluated by Spearman's and Kendall's Tau. Additionally, NAS algorithms and show that the GradSign-assisted NAS algorithms outperform their vanilla counterparts by improving the accuracies of best-dixcovered networks by up to 0.3%, 1.1% and 1.0% on three real-world tasks. Code is available at https: /tte:://gittin com JackF ram GradSign
random initialization state.
have integrated GradSign into four existing
INTRODUCTION
As deep learning methods evolve, neural architectures have gotten progressively larger and more sophisticated (He al. 2015 & Szegedy [2033] Krizhevsky al. 2017: Devlin al. 20019] Rumelhart et al. 1986 Srivastava et al. [014 Kingma & Bal 2017). making it increasingly challeng- ing manually design model architectures that can achieve state-of-the-art predictive performance. To alleviate this challenge, recent work has proposed several approaches to automatically discovering statistically accurate and computationally efficient neural architectures. The most common approach is neural architecture search (NAS), which explores comprehensive search space of potential net- work architectures that use set of predefined network modules as basic building blocks. Recent work shows that NAS is able to discover architectures that outperform numan-designed counterparts (Liu jet al. 2018a Sa Zoph& & Le 2016 Pham et al. 2018).
A key challenge in NAS is quickly assessing the predictive performance of a diverse set of candidate architectures discover performant ones. We refer to this task as model performance inference (MPI). A straightforward approach to MPI is directly training each candidate architecture on datasct until convergence and recording the achieved training loss and validation accuracy (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 training

---

Published as a conference paper at ICLR 2022
dataset, gradient-bused methods 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 sample-wise optimization landscape of a network. GradSign takes as inputs a mini-batch sample- somple-wise gradients evaluated at a random initialization point and outputs statistical evidence of network that highly correlates its well-trained predictive performance measured by accuracy on the entire dataset.
Prior theoretical results (Allen-Zhu al., 2019) show that the optimization landscape of randomly initialized network is nearly convex and semi-smooth for sufficiently large neighborhood. To realize its potential for MPI, we generalize these results sample-wise optimization landscapes and propose a quantity V to measure the density of sample-wise local optima in the convex areas around random initialization point. Additionally, we prove that both the training loss and generalization error of network are proportionally upper bounded by 2 under reasonable assumptions.
Based on our theoretical results, we design GradSign, an accurate and simple approximation of V. Empirically, we show that GradSign can also generalize to realistic setups that may violate our assumptions. In addition, GradSign is efficient to compute and easy to implement as it uses only the sample-wise gradient information of network at random initialization point.
Extensive evaluation GradSign on seven NAS benchmarks (i.e., NAS-Bench- 101, NAS-Bench-2011 and five design spaces of NDS) across three datasets (i.e., CIFAR-I0. CIFAR-I00 and ImageNet16 16 120) shows that GradSign consistently outperforms existing gradient- based methods all circum- stances. Furthermore, we have integrated 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 this insight, introduce new quantity V that provides an upper bound on both the training loss and generalization error network under reasonable assumptions.
To infer V, we propose GradSign, an accurate and simple estimation of v. GradSign enables fast and efficient MPI using only the sample-wise gradients of network initialization.
We empirically show that GradSign generalizes to modern network architectures and consis- tently outperforms existing gradient-based MPI methods. Additionally, GradSign can be directly integrated into variety of NAS algorithms to discover more accurate architectures.
2 RELATED WORK
2.1 MODEL PERFORMANCE INFERENCE
Table summarizes existing approaches to inferring the statistical performance of neural architectures.
Sample- based methods assess the performance of neural architecture by training it on dataset. Though accurate, sample-based methods require surrogate training procedure to evaluate each architecture. EconNAS (Zhou 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 al., 2018), to assess the predictive performance of a network (Chen et al., 2020a MMllor et 2021 Park et al. 2020). In particular, NNGP (Park et al., 2020) infers a network's performance by fitting its kernel regression parameters on training dataset and evaluating its accuracy 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 training convergence rate and generalization performance. However, this theoretical evidence is only guaranteed for extremely wide networks with specialized initialization mode. While the linear region analysis used in Mellor
2

---

Published as a conference paper at ICLR 2022
Table A summary of existing methods for model performance inference. The right four columns show (1) whether a method is based on theoretical results, (2) whether a method avoids expensive training process, (3) whether method is applicable to different model architectures, and (4) whether
method is applicable across different tasks.
Theoretical Insight
Training Free
Model Independent
Task Independent
Methods
Sample-Based
EconNAS
X
X
NNGP. TE-NAS,
/
X
Theory-Based
NASWOT, ZenNAS
Neural Predictor,
X
X
X
Learning-Baad -Based
One-Shot-NAS-GCN
Snip, Grasp, Synflow Fisher GradSign (this paper)
x
Gradient-Basse
al. (202], Lin al. (2021) and Chen et al. applicable to networks with ReLU activations (Agarap
(2020a) is easy to implement, such technique is only 2018
Learning-based methods train separate network (c.g., graph neural networks) to predict a net- work's accuracy (Liuu et al. 2018a Luo et al.) 2020 Dai et al., 2019 Wen et al. 2020; Chen jtt al. 2020b; (Siems et al., (020). 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-basse methods are generally task-specific and computationally prohibitive.
Gradient-based methods infer the statistical performance of a network by leveraging its gradient information initialization, which can be easily obtained using automated differentiation tool of today's '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 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 be effective as baselines in recent works (Abdelfattah el al.) 202 a Mellor et al., 2021: Lin et al. 202T). An
alternative stream of work (Turne et al.) 2019: 2021] Theis et al.) 20188) uses approximated second- order gradients, known as empirical Fisher Information Matrix (FIM), at random initialization point to infer the performance of network. Empirical FIM (Martens) 2014) is valid approximation of a model's predictive performance only if the model's 'ss parameters are a Maximum Likelihood Estimation (MLE). However, this assumption is invalid at a random initialization point, making FIM-hased algorithms inapplicable. A key difference between GradSign and existing madient-based methods is that GradSign based on 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-wist wise gradient information, while prior gradient-based methods only focus on gradients evaluated in full batch fashion.
2.2 NEURAL ARCHITECTURE SEARCH
Recent work (He et al. 2021 Cai et al., 2019 2018 Tan & Le 2019 Howard et al.) 2019) has 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 ar- chitectures randomly the search space. REINFORCE (Williams) 1992) moves a step forward by reframing NAS as reinforcement learning task where accuracy the reward and architecture generation is the policy action. Given limited computational resources, BOHB (Falkner et al. 2018) uses Bayesian Optimization (BO) propose candidates while uses HyperBand (BB) (Li 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 can be combined with existing NAS algorithms. We integrate GradSign into the NAS algorithms mentioned above and show that GradSign can consistently assist these NAS algorithms discover more accurate architectures on various real-world tasks.
and
2.3 OPTIMIZATION LANDSCAPE ANALYSIS
Inspired by the fact that over paramettttee 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
3

---

Published as a conference paper at ICLR 2022
10 0.0
10"
6
of
0
(a) Optimization landscape with sparser sample-wise local optima corresponding to
(b) Optimization landscape with denser sample-wise local optima corresponding to better J(0").
worse ((")).
Figure 1: Illustration of our thcoretical insight that denser sample-wise local optima indicate lower training losses. As the distances (00 02), 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 random initialization point, shown as the green areas.
deep learning theory (Brutzkus & Globerson 2017 Du al. 2018 Ge et al. 2017 & Yuan 2017, /ootaanokkotabi 201 2017] Allen-Zhu et al., 2019). Even though existing theoretical results for optimization landscape analysis rely on strict assumptions on the landscape's s smoothness, convexity, and initialization point, can leverage thcoretical insights to guide the design of GradSign. In addition, SGD-based optimizers trained from randomly initialized points hardly encounter non- smoothness non-convexity in practice for variety of architectures (Goodfellow et al., (014). Furthermore, Allen-Zhu et al. (2019) provides theoretical evidence that for a sufficiently large neighborhood of randomly initialized point, the optimization landscape is nearly convex and semi- smooth. 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 MPI by leveraging sample-wise optimization landscapes.
3 THEORETICAL FOUNDATIONS
3.1 INSIGHTS
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 sam- ples. 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 Fig- ure I Both Figure Ta and Figure 1b reach local optimum at 0" for the mini-batch objective (1( (x1), y1 ((fo- (ar2), 322)). However, the optimization landscape in Figure contaiisss a better local optimum Hr (i.e., lower J). This can be distinguished by analyzing the relative distance between local optima across training samples (i.c., |0 051 in Figure I.
For mini-batch with more than two samples, we sample wise local optima density measurement defined in Section 3.2 to represent the overall closeness of sample-wise local optima. Intuitively, the distances between the local optima across samples reduce (shown as the red areas in Figure [ there a higher probability that the gradients of different samples evaluated at a random initialization point have the same sign (shown the green areas in Figure [ Driven by this insight, GradSign to infer the sample-wise local optima density V statistically. The design of GradSign 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 formal derivation of our theoretical results in Section 3.3 and present GradSign in Section
propose
3.2 PRELIMINARIES
We use = (ZT, yi) hemn to denote training samples, where each æ; E Id is a feature vector, and y: is the corresponding label. We use 1(gi. yi) to represent a loss function where di is the prediction of our model. We use so(.) IRd IRo denote the model parameterized by 0 and Og IR. m to
4

---

Published as a conference paper at ICLR 2022
denote random initialized parameters where m is the number of model parameters. Bold font constant denotes a constant vector such as 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 an assumption that there exists a neighborhood Fo, for a random initialization point 6g in which sample-wise optimization landscapes almost convex and semi- smooth. Note that our assumption is weaker than that of (Allen-Zhu et al. 2019) since their analysis is focusing on the overall optimization landscape while we only consider the sample-wise optimization landscape which is a simpler case. We use {0] he[n: E To to denote local optima in the convex areas attached the i-th sample near the initialization point 8g. Under this assumption, the overall optimization landscape is also convex and semi- within the neighborhood Te, as additive operations preserve both. We use 0* to denote local optimum within To, for the mini-batch optimization landscape. Note that 6* always lie in the convex hull of {Ø] )ejn)- Second, assume that only gradient-based optimizers are used during training. Thus the optimizer eventually converges to 8* Third, our theoretical analysis assumes that every Hessian the set (V²I(fo(1a)) Vv regime (Jacot et al. 2018). Section 5 shows that our method generalizes well to real-world networks that may violate this assumption.
[m].0 [ is almost diagonal as in the Neural Tangent Kernel (NTK)
Sample-wise local optima density. We use sample-wise local optima density to represent the relative closeness of {0; Jeejn]- Given dataset S {(1 3:) Jijj) an objective function (() Vs), and
model class f-), we use (f,, (-)) measure the average distance between the local optima across samples {0] heE[M) near random initialization point 0n:
VH n
ss,, =
10
0j1lz
(1)
H E IR is smoothness upper bound: vk E [m]. E [m], (T)(ff(;;; M))k. S H. This upper bound always exists due to the smoothness assumption. Intuitively, (f, (.) can be interpreted as the mean Manhattan distance with respect to each pair of {0; Jiejn] normalized by the inverse of the square root of the smoothness upper bound. The denser {0; He(n are, the smaller (fe, (-)) is. In an ideal case, (S,, (-)) = 0 when all local optima are located at the same point.
3.3
MAIN RESULTS
We show the local optimum property of sample-wise optimization landscapes in the following lemma.
Lemma 1 There exists saddle point in sample-wise optimization landscape and every local optimum is a global optimum.
Using Lemma we can draw a relation between the training error V.. (S, (-)) using the following theorem.
1 n E, ((f((z))))))) y:) and
Theorem 2 The training error of network on a dataset J = E, ((fo(z:), vi) is upper bounded n² by 2 (f), and the bound is right when V s.s,(foo 0.
Finally, we show that s. (fe, (-)) also provides upper bound for the generalization performance of a network measured by population loss.
Theorem Given that (z.. 1110 [ is bounded by 0² where 0% is local optimum
atlached to the convex area near 00 for ((fo(z)) v.). With probability 1 8, the true population
loss is upper bounded by 2 V3, (-)
A formal proof of all theoretical results is available in Appendix
A.2
Main takeaways: A key takeaway of our theoretical results is that v (..( (-)) closely relates to an upper bound of the training and generalization performance of network. Albeit theoretically sound, V (ffe, (+)) is intractable to be directly measured. Instead, we derive a simple yet accurate metric to reflect V (fo, (-)), which present in the next section.
Gradient descent with infinitesimal step size
5

---

Published as a conference paper at ICLR 2022
4 GRADSIGN
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 quantity to statistically reflect the relative value of (So (.))- Specifically,
(ss((fo,()) & C ΣΣ 3
= sign([Vol((((z)))
(2)
where C' is constant and k is the vector index. Detailed derivation is given in Appendix A.2 Using the above relation, we can infer V V. (-)) by directly measuring the signs of the gradients for mini-batch of training samples at randomly initialized point instead of going through end-to-end training process.
To enable more efficient calculation of (s,,( (-)), we make further simplification and use the following sample observation:
Σ
Σ sign (Vol([V(()))) w:)lo))))
(3)
infer the true probability whose relation is given by:
Σx Eng
(4)
π
Σ [ign((Vol(66crr)__))llll))
The proof of this simplification is included in Appendix A.2
Given the above relationship,
formally state our algorithm pipeline in Algorithm Note that a higher GradSign score indicates better model performance we have inverse correlation in Equation
Algorithm 1: GradSign
Result: GradSign score Ty for a function class fe
Given S {(rri, yt) [e)]) randomly select initialization point 0o:
Initialize g/n, m]]
for i = 1,2,.... , do
for k = 1. m do g k| = sign((Voo(fo(xx)))))
end
end
Ty = Σx Σ, gii
return of
EXPERIMENTS
In this section, empirically verify the effectiveness of our metric against existing gradient-based methods on three neural architecture search (NAS) benchmarks. including NAS-Bench- 101 (Ying al. 2019), MAS-Bench-201 (Dong & Yang 2020) and NDS (Radosavovic et al. 2019 Theory- based, sample-based and lcarning-basee 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) al. 2018), grasp (Wang et al. 2020), fisher [Turner al., 2019), and Synflow. In addition, we also include grad norm as heuristic method and one-shot MPI metric NASWOT(Mellor et al. 202T). Since all gradient-basee based methods share a similar calculation pipeline (i.e., evaluating the gradients of mini-batch at random initialization point), we set the initialization mode and batch size be the same across all methods to guarantee fairness. Experimental setup details are included in Appendix A.3 To align with the experimental setup of prior work (Abdelfattah et al. 2021b
All datasets have consented for research purposes and identifiable personal information is included.

---

Published as a conference paper at ICLR 2022
Mellor et al. 2021>, use two criteria to evaluate the correlations between different metries and test accuracies across approximately 20k networks:
Spearman's (Daniel al. 1990) characterizes the monotonic relationships between two variables. The correlation score is restricted in range [-1, 1], where p = 1 denotes a perfect positive monotonic relationship and p -1 denotes perfect negative monotonic relationship. Following prior work, we use Spearman's 's p to evaluate gradient-bad -based methods on WAS-Bench-Ile 101 and MAS-Bench-2011
Kendall's Tau. Similar Spearman's 's p correlation measurement, Kendall's Tau is also restricted between [-1, IJ. While Spearman's p is more sensitive to error and discrepancies, Kendall's Tau is more robust with smaller gross error sensitivity. We use Kendall's Tau to quantify the correlation between one-shot metric scores and model testing accuracies over the NDS search space.
5.1 JAS-BENCI--101
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 each architecture in the search space, which we use to calculate the corresponding Spearman's p. We use randomly sampled subset with approximately 4500 architectures of the original search space and a batch size 64 in this experiment. Table 2 summarizes the results. GradSign significantly outperforms existing gradient-base based methods and heuristic approaches and improves the Spearman's 's score by 25% compared to the best existing method (0.363 - 0.449).
Table 2: Performance of existed MPI methods (gradient-bawsl baased + NASWOT) on NAS-Bench- 101 evaluated by Spearman's p.
Dataset grad norm snip grasp fisher Synflow NASWOT GradSign
CIFARIO
0.263 0.189 0.315 0.3 0.363
0.324
0.449
5.2 NAS-BENCH-201
with different search space, contain- NAS BencBenhhB2- 1 is extended version of evaluated across three datasets: CIFAR-10, CIFAR- ing 15,625 cell-based candidate architectures 100 (Krizhevsky) 2009) and ImageNet 16-120 (Russakovsky al. 2015). The benchmark provides the test accuracies on the three datasets for all candidate architectures in the search space. We evaluate Spearman's P scores for GradSign and existing gradient-based methods. The experiments were 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 GradSign consistently achieves the best performance across all three datasets and improves the Spearman's 's p scores by ~ 4% over the best existing approaches. This improvement significant as the more Spearman's 's p approaches 1, the more difficult it can be further improved.
Table 3: Performance of existed MPI methods (gradient-based NASWOT + ZenNAS) on NAS- Bench-201 evaluated by Spearman's p.
Dataset CIFARIO
ZenNAS
grad norm snip
grasp
fisher
Synflow NASWOT
GradSign
-0.016
0.594
0.595
0.51
0.36
0.737
0.728
0.765
CIFAR100
-0.041
0.637
0.637
0.549
0.386
0.763
0.703
0.793
ImageNet16- 120
0.032
0.579
0.579
0.552
0.328
0.751
0.696
0.783
We further select 1000 architecture candidates randomly in the NAS-Bench-201 search space and visualize their testing accuracies against GradSign scores in Figure 2 F shows 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.
5.3 NAS DESIGN SPACE (NDS)
NDS is a unified searching framework that includes five different design spaces: NAS-Net ZZoph et al. 2018), AmoehaNet (Real al., 2019), PNAS (Liu et al. 2018a), ENAS (Pham al. 2018).
7

---

Published as a conference paper at ICLR 2022
2018b). Each space contains approximately thousand networks 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 I GradSign significantly and consistently outperforms all other MPI methods in all five design spaces.
DARTS (Liu et al.
Table 4: Performance of existed MPI methods five design spaces in NDS trained over CIFAR-10
evaluated by Kendall's Tau.
DARTS
ENAS
PNAS
NASNet
Amoeba
grad_norm norm
0.28
-0.02
-0.01
-0.08
-0.10
Synflow
0.37
0.02
0.03
-0.03
-0.06
NASWOT
0.48
0.34
0.31
0.31
0.20
GradSign 0.54
0.43
0.40
0.31
0.24
5.4 ARCHITECTURE SELECTION
We evaluate whether GradSign can be directly used to select highly accurate architectures a NAS search space. To pick top architecture, randomly sample N candidates in NAS search space, choose the one with the highest GradSign score, and measure its validation/test accuracies (tt) We compare GradSign with Synflow, NASWOT, Random, and Optimal, where Random uniformly samples architectures the search space, while Opt i always chooses the best architecture across N candidates. The results" 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 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.
Table 5: Mean + std accuracy evaluated on
All results are averaged over 500 runs. All searches conducted on CIFAR-10 while the selected architectures evaluated CIFAR- 10, CIFAR-100, and ImageNet16-122 120. N in parenthesis is the number networks sampled in each run.
CIFAR-IO
110
ImageNet 120
Methods
Validation
Test
Validation
Test
Validation
Test
1ynflow(N=100)
89.83 0.75
93.12:1.522
69.8911.87
69.94 1.88
41.4444.1442.2::444
NASWOT(N=100)
89.55
02.81+0.99
6.73
42.81 6..48 13.1033.16
11000
89.69
92.96-L0.81
69.98
1.28
44.44 43.95 2.05
GradSign(N=100)
89.84=0.61
93.31:00477
1..22=1.32
70.3311.28
22.7:22.7844.42122
Random
83.20+13.28 86.61
60.70+12.55
33.44499
Opt Optimal (N-100) 91.05=0.28 93.8440.23 70.4 71.56110.8
45.37:0.61 45.67:00.4
5.5 GRADSIGN-ASSITTI NEURAL ARCHITECTURE SEARCH
Besides evaluating GradSign on the Spearman's '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. Specifically, we integrate GradSign into each NAS algorithm by replacing the random selection of architectures with trradSign-assisted selection. We name these GradSign-assisted variants G-REA, G-REINFROCE, G-HB, and G-RS, and describe their algorithm details Appendix
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 MAS-Bench--211 and report the validation and test accuracies of the best-discovered architecture in each run. Following prior work (Mellor et al. 202 Dong & Yang 2020), all searches are conducted on the CIFAR- 10 dataset with time budget of 12000s while the performance is evaluated on CIFAR-10, CIFAR- 100 and
the results for NASWOT are referenced from their paper (ellor al. 2021
8

---

Published as a conference paper at ICLR 2022
ImageNNet16-120. The baselines also include A-REA (Mellor et al. 2021), ), variant of REA that uses the NASWOT scores at the initial population selection phase.
Table 6 shows the results. The GradSign-assiseet NAS algorithms outperform their counterparts by improving test accuracy by up to 0.3%, 1.1 %, and 1.0% on the three datasets.
Table Mean + std accuracy evaluated over JAS-Bench-201. All results are averaged over 500 runs. To make a fair comparison across all the methods, the search is performed on CIFAR- 10 dataset while the architectures" performance are evaluated over CIFAR-10. CIFAR- 100 and ImageNet 6- 120. All the methods have a search time budget of 12000s. Note that the benchmark results might not match with the original paper as we have run all the experiments from start in a environment different
from Dong & Yang (2020).
CIFAR- 10
CIFAR- 100
ImageNeet6-122 120
Methods
Validation
Test
Validation
Test
Validation
Test
REA
91.08 1..45
93.45
1.35
1..64
44.90 1.20
45.25
A-REA
91.20=0.27
71.95
45.70=1.05
G-REA
91.27=10.88 94.10:10.52
72.64:1.57
7..70=1.50
45.69-1.33
45.7=1132
RS
90.93-0.37
93.72:10.38
70.9611.12
71.07=1.07
44.47=1.08
4..61
G-RS
91.24:10.1
94.02.10.21
72.1510.77
72.70
45.38-1079
45.7710.79
REINFORCE
90.32.10.89
93.21
70.03
70.1411.73
43.3742.09
43.6411.24
G-REINFORCE
90.47:10.55
93.37-10.47
1..00
70.20
44.33
4..0
BOHB
90.84+10.4
F3.64
1..8
70.92+1.26
41.3
44.50
G-HB
91.18+0.22
0.225
71.92+
71.99
0.85
45.29
0.84
45.53
CONCLUSION
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 V (s,((Ja,()) to quantitatively characterize the potential of a model fo(-) at a random initialization point On based on our theory results. Finally, we design the GradSign metric to statistically infer the value of (Se,( (.)) to give out our final score for model performance inference. Empirically, we have demonstrated that our method consistently achieves the best correlation with 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. In addition, one of the future work of GradSign can be adding normalization across different architecture classes to tackle the clustering problem in Figure 2
true model performance among all other gradient-base
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving. Michael Isard, et al. Tensorflow: system for large-scale machine learning. In 12th (USENIX) symposiun operating systems design and implementation (LOSDI) 16), pp. 265-283, 2016.
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Lane. Zero-cost proxies for lightweight nas. arXiv preprint arXiv:2101.08/34 2021a.
Mohamed S. Abdelfattah, Abhinay Mehrotra, Lukasz Dudziak, and Nicholas D. Lane. Zero-Cost Proxies for Lightweight NAS. In International Conference on Learning Representations (ICLR), 2021b.
Abien Fred Agarap. Deep learning using rectified linear units (relu). arXiy preprint arXiv:1803.083: 2018.

---

Published as a conference paper at ICLR 2022
Zeyuan Alue Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International conference on machine learning, pp. 605-614. PMLR, 2017.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint urXiv:/812.00333 2018.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network 2019.
and specialize for efficient deployment. arXiv preprint
Tianlong Chen, Jonathan Frankle. Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint arXiv:2007.12223, 2020a.
Xin Chen, Lingxi Xie, Jun Wu, Longhui Wei, Yuhui Xu, and Qi Tian. Fitting the search space of weight- nas with graph convolutional networks. arXiv preprint arXiv:2004.08423 08422, 2020b.
Xiaoliang Dai, Peizhao Zhang, Bichen Wu, Hongxu Yin, Fei Sun, Yanghan Wang, Marat Dukhan, Yunging Hu, Yiming Wu, Yangqing Jía, et al. Chamnet: Towards efficient network design through platform-aware model adaptation. Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp. 11398-11407, 2019.
Wayne W Daniel et al. Applied nonparametric statistics. 1990.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-200. Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.00::: 2020.
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learss one-hidden-layer cnn: Don't be afraid of spurious local minima. In International Conference on Machine Learning, pp. 1339-1348. PMLR, 2018.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization at scale. In International Conference on Machine Learning, pp. 1437-1446. PMLR, 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:
2018.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one- hhdden-laaee neural networks with landscape design. arXiv preprint /7 2017.
Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. arXiv preprint arXiv: arXiv:1412.0 1412.6544, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
Xin He, Kaiyong Zhao, and Xiaowen Chu. Automl: survey of the state-of-the-art. Knowledge- Based Systems, 212:10662) 2021.
Andrew Howard, Mark Sandler, Grace Chu, Liang- Chich Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, Quoe V. Le, and Hartwig Adam. Searching for mobilenetv3. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), October 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift, 2015.
10

---

Published as a conference paper at ICLR 2022
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv: 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Ily Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60(6))84-99)) 90, 2017. ISSN 1557-7317. doi:
10.1145/3065386 URL/ttp: doi org 11w. 3065386
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity, arXiv preprint arXiv:1810.02340,, 2018.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):676568166 2017.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. arXiv preprint arXiv: / 705.09886, 2017.
Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-nas: A zero-shot nas for high-performance image recognition. Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 347-356, 2021.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Fei-Fei. Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European conference computer vision (ECCV), pp. 19 34, 2018a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search, arXiv preprint arXiv:1806.0900 2018b.
Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu. Semi-supervised neural architecture search. arXiv preprint arXiv:2002. 10389, 2020.
James Martens. New insights and perspectives on the natural gradient method. arXiv preprint urXiv::412.111 2014.
Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J. Crowley. Neural architecture search without training, 2021.
Xuefei Ning, Yin Zheng, Tianchen Zhao, Yu Wang, and Huazhong Yang. A generic graph-based neural architecture encoding scheme for predictor-based nas. In Computer Vision-ECCe -CCo 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XIII 16, pp. 189-204. Springer, 2020.
Daniel S Park, Jachoon Lee, Daiyi Peng, Yuan Cao, and Jascha Sohl-Dickstein. Towards angp-guided neural architecture search. arXiv preprint arXiv:0011.06006 2020.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference Machine Learning, pp. 4095-4104, PMLR, 2018.
Ilija Radosavovic, Justin Johnson, Saining Xie, Wan- Yen Lo, and Piotr Dollár, On network design spaces for visual recognition. Proceedings of the IEFF/CVF International Conference on Computer Vision, pp. 1882-1890, 2019.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence. volume 33, pp. 4780-4789, 2019.
11

---

Published as a conference paper at ICLR 2022
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by prok-propggating errors. nature, (23()088) 1986.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, (15(3):211-2) 1-222, 2015.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pp. 4558-4566. PMLR, 2018.
Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas- bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008.09777 2020.
Mahdi Soltanolkouabi. Learning relus via gradient descent. arXiv preprint
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, (5(66):92991199) 2014. URL http:// httt:://jmlr.oret www.org/pppes/vvi... /v15
erivastaval4an html
Mingxing Tan and Quoe Le. EfficientNet: Rethinking model scaling for convolutional neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6105-6114. PMLR, 09-15 Jun 2019. URL
mlr
press/v97/eit tanl 9a. html
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint 20xiv:2000.05466,, 2020. 2020.
Lucas Theis, Iryna Korshunova, Alykhan Tejani, and Ferene Huszár. Faster gaze prediction with dense networks and fisher pruning. arXiv preprint /00.0/000.05777 2018.
Jack Turner, Elliot J Crowley, Michael O' Boyle, Amos Storkey, and Gavin Gray. Blockswap: Fisher- guided block substitution for network compression on a budget. arXiv preprint arXiv: (44i::9900041111 2019.
Jack Turner, Elliot J Crowley, and Michael FP O' O'Boyle. Neural architecture search as program trans- formation exploration. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 915-927, 2021.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020.
Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv: 1059, 2019.
Wei Wen, Hanxiao Liu, Yiran Chen, Hai Li, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. In European Conference Computer Vision, pp. 660-676. Springer, 2020.
Ronald J Williams. Simple statistical gralient- algorithms for connectionist reinforcement learning. Machine learning, ((3):29-256,, 1992.
Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and generaliza- tion deep neural networks. International Conference on Machine Learning, pp. 10462-10472. PMLR, 2020.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- bench-106 101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pp. 7105-7114 14, PMLR, 2019.
12

---

Published as a conference paper at ICLR 2022
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arxiv:661.033500 2016.
Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi, Xuesen Zhang, and Wanli Ouyang. Econas: Finding proxies for economical neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1 11396-11404, 2020.
Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv:661..0157,, 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018.
13

---

Published as a conference paper at ICLR 2022
A
APPENDIX
A.1
FIGURE
CIFAR-10
CIFAR-100
ImageNet16-120
70
Model accurary
accuracy
60
Model accuracy
40
70-
50
30
40
50
30
20
30
20
10
10
0.0 0.2 0.4 0.6 0.8 1.0 1.2
0.0 0.2 0.4 0.6
0.2 0.6 1.0 1.2
GradSign metric score
GradSign metric score
GradSign metric score
Figure 2: Visualization of model testing accuracy versus GradSign metric score on CIFARIO, CIFARI00, ImageNet16-1200
A.2 PROOF
Lemma 1 Proof: For single training sample (s,, Yi), minimize its objective function
((fe(z;), y4) with gradient descent:
@l(fo(zi)...) fx(
Vol(fo(zi)..))
(6)
(sa(x:)
At any local optimal point 0j, we have Vol(So(x;), vi)o; O, but fz(x;) O for conventional neural architectures with least one dense layer Therefore, show ((.f)
0fo(z;) lor must be equal O. For the commonly used objective functions, such as Mean Squared Error Loss and Cross Entropy Loss, this derivative is equal to (z) 3r), where C' is non-zero constant. Hence we have fo; (I;) = Y and ((for (z,), 31) at local optima 8r, which makes 0 also a global optima as it is impossible to obtain a lower loss value for this single sample. In addition, at local optima 67, we have:
Vol al(So(Ia)). (b(x;))
VOl(Io((ss.v.)
0fo(1,)
(((f((a))))) fo(.)))6(..)T
@l(f((z)). 0fe(m))
(8) The above equation implies that (z,()( yi) a positive semi-definite matrix, since C > 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
f (x,)
0fa(x.)²
C (x:)
Theorem Proof: Recall that 0* denotes a local optima of J which could reached by a gradient- flow based optimizer start from lg. Since Og is randomly sampled and [V*[(fo(zx), Me )). S H, we have:
J
Σ I(fo (zx).
(10)
n
1
H. - 110 - -07113
(11)
n
Σ 110 - 0,11
(12)
H Σ 10 - 07
(13)
22 s. (-).
(14)
*The gradient values corresponding the bias of the last dense layer are always non-zero.
14

---

Published as a conference paper at ICLR 2022
where Eq 10
Eq 11 uses the basic property of the smoothness upper bound H. and the fact that
each local optimum 8 satisfies ([fo; (2+), 3/) 0. Eq I1 + Eq uses Jensen Inequality for square
root operators. Eq 12
Eq 13 is derived from the fact that for each dimension in (0* 07) we have:
|00
Σ 07]x
(15)
Otherwise, 0" dose not lie in the convex hull of {0] he(nl which contradicts with our assumption stated in Section 3.2 The bound is tight when 0 = 0j. Vi,j E [n].
Eq 10 Eq 11
As we have (²I(fo(z;) us) 3 HTl and I(fo (2:), Us) O, Vol = 0.
we could derive the following inequality:
s [[fo (24) ve) Vol(for(z)). 10" -07) + H
I(fo (1)).
2 110
0:11
(16)
H
110 -0712
(17)
we thus have E1 (x:), Ui) S 2n E, H 110 1/
Theorem 3 Proof: Let [ (. [ ([ʃ (zu), M.)] denotes the true population error. With probability 1- 6, we have:
E (. vw)l S
HE, H. 1211
(18)
H
00
-0711
(19)
Vnd
n n (-))
(20)
Vnd
where n and are constants, S is training dataset, and D denotes its underlying data distribution. This implies that (fe, (-)) is an accurate indicator for the true population loss. Eq 18 - Eq 19
uses Chebyshev's inequality, while Eq 19 20 uses the same inequality derived in Claim 2.
Algorithm Proof: Given that sample-wise local optima {[0)), E [n]] are contained in the convex
area around fy. We derive the following property:
sign(10; Oulk) sign (Vollfo(xx)
(21)
Since 6g is randomly chosen initialization point, without loss of generality, we assume 0g is sampled from hypercube [-a,at a). Thus we have:
|0 [0ā]al
([sign((Vol(fo((z)).aa)) # (Vo((Vl((l(e,))))))llll
(22)
2a
Where P(sign((Vol(fa((z)))))))ll * for [Vol(fe(x;), vi)lall and [V)((f(())) Mj)le,le having different signs. Notice that we
1;)lo, denotes the probability
have completely dropped the dependency for 0; at this point and can simply infer from sign( (en([Volfoozz)) v.)...k). To complete our proof:
VH.
(s,((fo(())
10; 07112
(23)
[
2av H
P(sign((Vo(((((())))))))) (in( 1)))))))))))) 1(99))
n²
P(sign((Vo(((((()))))))))) o/tp:///0...llllllooooeoe/////da )0.5)
15

---

Published as a conference paper at ICLR 2022
Simplification
Proof: for each i.j and given k (Volgn((VVolfe(ee) 3.)le,la = ( (idgs),,,,),. vy))),le) using:
could
estimate
sign (Va((fo(z)) y.llell) + sign((Vol(fe(zz)) 11)01(1))
(26)
which is valid (not equal to zero) only when (ign((Vo(ffo(z.). 91) (:)lk
sign( (Vl(ff )o, Suppose we have p positive and n-p negative sign( (Vol(fo(z) vi)ao, for samples, since we only care about samples share the same sign, the original probability
(m-2p)" Thus only need measure the quantity In 2pl which simply equals to [E, (.))e..)
estimation is (n- +ppp)
A.3 EXPERIMENTS SETUP
The code we used during experimentation was mainly based on existed code base Abdelfattah et al. (2021b); Mellor et al. (2021 [ Abdelfattah 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- which is training free, we don't tt need to split our dataset. For Spearman's 's correlation measurement on MAS-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 128, also to match the batch size other baselines (NASWOT). We use Pytorch default parameter initialization for all architectures. Random seed in correlation experiments set to 42 which also randomly chosen. For accuracy experiments, results summarized over 500 runs whose random seed chosen randomly for each run. For the correlation evaluation of each individual architecture, we only use one 6g for minimizing computational cost. Our approach can be easily generalized to average of multiple oos and can trade-off between efficiency and accuracy.
A.4 ADDITIONAL RESULTS
Sample-based: Fig compares EconNAS, a sample-based method, with existing gradient- methods on MPI. Results of EconNAS are referenced from (omddeelfaattah et al. (2021b). To achieve similar MPI performance as GradSign, EconNAS needs 500 minibatches of samples for each candidate's 's proxy training, while all gradient- based methods (including GradSign) require only one minibatch. By increasing the number of minibatches, EconNAS achieve higher Spearman's 's p scores, which eventually converge to 0.85. At that point overfitting takes place and the score cannot be further improved.
16

---

Published as a conference paper at ICLR 2022
Epochs
1
3
4
6
8
9
10
11
0.85
0.80
ggradsign
0.75
econas
synflow naswot
0.70
Spearman
0.65
snip
0.60
grad _rad_norm
norm
0.55
grasp
0.50
0.45
econas
0.40
500
1000
1500
2000
Evaluation Cost (number of minibatches)
Figure Comparison with sample- methods (EconNAS) on NAS-Bench-200 across CIFAR- 10. EconNAS requires more than 500 minibatches to have a better performance than GradSign while gradient-based methods only require minibatch.
Learning-based: compares GradSign and existing Gearning-aased methods (MIP, LSTM, and GATES) on the Kendall's s Tau correlation score. The MLP, LSTM, and GATES 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) 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-22 201 and the GradSign's score averaged over all three datasets (CIFAR-10 10, CIFAR-100 100 and ImageNet16-122 as (Ning et al. 2020 does not provide which dataset is used for calculating Kendall's Tau.
To achieve 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 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 mini- batches 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.
Table 7: Comparison with learning-bass based methods (MLP, LSTM and GATES) NAS-Bench-201. GATES-1 represents GATES predictor with only one layer and GATES-2 denotes GATES predictors with more than one layers.
Kendall's Tau Average minibatches per sample
MLP
0.5388
1959
LSTM
0.6407
978
GATES-1
0.45
1959
GATES-2 0.7401
195
GradSign
0.6016
17

---

Published as a conference paper at ICLR 2022
We also includes the evaluation of GradSign for both MPI correlation performance and GradSign- assisted NAS algorithms on the latest version of NAS-Bench-20D Bench-201 (NATS-Bench) across three datasets (CIFAR-IO 10, CIFAR- 100 and ImageNet16-122) against hyper-paramete tuning as long as the trained networks can converge to near optimal. Also notice that trradign-assisted NAS algorithms could only achieve better accuracy but lower variance as well compared to their non-assisted counterparts.
in Table g Table g Results show GradSign is robust
Table 8: Spearman's 's p evaluated on the latest version of NAS-Bench-2D0 (NATS-Bench)
CIFAR-I0
CIFAR-I00
ImageNet16-120
NAS-Bench-201
0.765
0.793
0.783
NATS-Bencch
0.760
0.792
0.784
Table Mean + std accuracy evaluated over NATS-Benchs All results are averaged over 500 runs. To make fair comparison across all the methods, the search is performed CIFAR-100 dataset while the architectures' performance are evaluated over CIFAR-I0, CIFAR-100 and ImageNet 1-20 All the methods have a search time budget of 1200ss. Note that the benchmark results might not match with the original paper as we have run all the experiments from start in environment different
from Dong & Yang (222)).
CIFAR 10
CIFAR 100
ImageNet16. 120
Methods
Validation
Test
Validation
Test
Validation
Test
REA
91.06110.49
93.8410045
1.35
71.60 44.82+1.23
1..18
G-REA
91.35++0.35
94.15++0.32
72.67+1.05
7.96 4.96
45.9
RS
90.9510.28
93.77:0.26
71.01
71.15
44.58=0.95
44.73
G-RS
91.23:10.22
94.02++..22
72.12+0.82
72.1510.78
45.43=0.74
45.83+1.800
REINFORCE
90.92-10.38
93.71
71.04
71.17
44.96
44.80
G-REINFORCE
91.20-10.23
93.9810.23
71.9310911
72.0510.89
45.28-1077
45.6410.86
To demonstrate the potential for GradSign in more complicated computer vision task, we compare the performance GradSign with ZenNAS following their setups and search space. Due to the limitation of computational resources we only run 10000 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. Though the top-1 validation accuracy of GradSign in the first 20 epochs is slightly better than Zen, we should note that this process can highly depend the random seed for evolution search phase. 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 architecture complexity related score which is both dataset independent and initialization independent, it can be too general and results in low Spearman's 's p shown in Table
the original setup in ZenNAS could take up months for training 480 epochs ImageNet-1k
18

---

Published as a conference paper at ICLR 2022
ImageNet-Ik -kk
GradSign
60
Zen
50
Top-1 Acc
40
30
20
10
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
epochs
Figure 4: Comparison with ZenNAS in their search space on ImageNet-1k, Ik. Due the limitation of computational resources, we only run 10000 evolution iterations and 20 epochs to train the selected architecture. We plot the top-1 prediction accuracy along training for methods (ZenNAS, GradSign).
A.5 GRADSIGN ASSISTED NAS ALGORIHTMM
19

---

Published as a conference paper at ICLR 2022
Algorithm G-REA
Result: Find the best performing architecture given the time constraint for 12000s
Population = []:
History = []:
population_sin
sample_size;
pool_size;
for 1, population size do
model = random.arch():
model.acc, model.time cost emooem):el);
appulaation.ppeed moodel);
Hissory..ppenndmodel)
end
while not exceeding time budget do
Sample []:
for 1, 2, ... ,sample_siz do
|
end
parent mae_mmaxa_aaaaaa aataa_aacc(Sampee). GradSign_pool= = []:
for 2, ppollppol_stte sizee do
GradSign assisted part */
model = mutate metaaeeaaachtpaaaaeeeee arch(parent);
model.score GradSign(model))
GiraSiign_poolappenddmmdeell
end
child 1aa=mmax_saaaa score(GradSign_
Population.appendee
Hiistory.apeendchhie
pnrplaation.poleffiii
end
return max_aem 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 budger do GradSign soiiign_pooo_-_ = []:
for 1, 2. ... -poo__iize do
GradSign assisted part */
model = random aachoommarrhhh_a
model.score GradSign(modde)); GradSiggupoollapeedd(neee))
end
arch max_ max_ssore(GrradSinnnpo arch.ace eval(arch) History.append(arch);
end
return max_aco(Hissorry;
20

---

Published as a conference paper at ICLR 2022
Algorithm G-REINFORCE
Result: Find the best performing architecture given the time constraint for 12000s
History = []:
pool_size;
policy Teg:
Reward = []:
baseline;
while not exceeding time budger do
arch geeegnnteeecchheeee o;);
GradSign_pool []:
for 1,2, ... _poo__iiee do
/x GradSign assisted part */
child mutate arch(arch);
child.score = GralSign(child));
GradSign_ poo........eppcdccchl)))
end
arch = max max__scoreea_ SooreeGradSig_Paae
arch.ace eval(:rch);
I= arch.ace;
aistorr..ppeend(arch)
Reward.appennd())
baseline (pdate baseline.updatter)):
0.+1 0: + VoEns, baseline]
end
return max_acc(Historr): return
Algorithm 5: G-HB
Result: Find the best performing architecture given the time constraint for 12000s
Input: budgets bmnn and 6max. 7);
Smax [log, bunss
bmin
score [oore_lst==10
pool_size;
for s E {smax, -m 0fddd do
config_ spaceesspcee__ee = [];
set = Smax-1 1 17"1:
while sizeoftconfig_spaee
do
GradSign_pool = 0]:
for 1,2, ... -pool_size do model = random _rchaa if model in score list then mooel.score score score_list lis][olll
GradSign assisted part +/
else
model.score GradSign(model); end GradSign_pool htwpigg___ool.pppemmmmmeelll end arch max laamma_sssossaaaaa score(GradSign pooo);
score_list[modes scoee
config (pace..ppend(arch):
end
SH on them with initial budget as 17" bmaxi
end
return best evaluated architecture:
21


Reviews:
[{"review_id": "VegKFbDHPv", "reviewer": "Reviewer_H9Ev", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The proposed metric is efficient to compute. It only requires the gradient information of a minibatch at a random initialization point.\n2. The underlying theory is sound. The proposed metric is backed by theoretical insights.\n\nWeaknesses:\n1. In the evaluation, the paper only compares GradSign with gradient-based approaches. I would like to see a comparison against other sample-based, learning-based approaches as well. You can compare the prediction accuracy and time cost of each method and show the trade-off. For example, a sample-based approach can be more accurate but takes 10x more time than GradSign.\n\nAdditional questions:\n1. How does the hyperparameter of training (e.g., learning rate) affect the prediction accuracy of GradSign?", "summary_of_the_paper": "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.\nExperimental results show that GradSign can generalize well to real-world networks and outperform state-of-the-art gradient-based methods for model performance inference.", "summary_of_the_review": "This paper introduces a simple yet effective way for model performance inference. It outperforms existing gradient-based approaches in almost all experiments. I recommend accepting this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OVxnEQIaa_2", "reviewer": "Reviewer_YHPS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Paper is clearly written and experimental results are convincing. The idea of Gradsign is novel and integrating it to existing methods seems to yield improved performance. \n\nI have some questions: \n\n1) Does eq (2) have an intuitive meaning? Is so, can you pls explain it. \n2) Table 1 shows that gradsign is task independent. Do the results generalise to other modalities such as text? Are there any benchmarks based on text datasets. ", "summary_of_the_paper": "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. \n\nAuthors 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. ", "summary_of_the_review": "\nThe problem of automatically discovering efficient neural architectures is the foundation of work on AutoAI. From that perspective this is a nice and important piece of work that seems to have theoretical foundation and good practical performance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NJgcgh-832J", "reviewer": "Reviewer_CHXp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I am quite intrigued by the method. It's elegant and simple and seems to perform well. I do have some reservations around the execution and presentation of the work as listed below. That's why it's not a clear accept for me at this point. \n\n### Strengths\n\n* Well-written and natural to follow\n* Interesting theoretical results and derivation. I don't enjoy reading through many theoretical results as they are often inaccessible. So I do appreciate the very clean and insightful presentation of the results. \n* Good experimental performance (although missing a few comparisons potentially).\n\n### Weaknesses\n\n1. **NAS vs Pruning**: I think the authors mix weight pruning and NAS throughout the paper. This is really confusing and while pruning and NAS have lots of overlap I don't think it's appropriate for this paper. Their main contribution is a Model Performance Inference (MPI) score and as such much more suitable for the NAS framework (evaluating architectures for their performance on some target task). \n\n2. **Pruning at initialization vs MPI scores**: (related to 1.) How can you compare against `SynFlow` and similar metrics that are designed for *weight pruning* at initialization? This seems like a strange comparison. I understand that the scores are compatible but could you provide some more context on why this is a useful comparison.\n\n3. **Related work**: I think the authors need to include a few additional citations that they are missing. For example, most of recent advances in NAS are missing such as OFA ([Cai et al., 2019](https://arxiv.org/abs/1908.09791)), ProxylessNAS ([Cai et al., 2018](https://arxiv.org/abs/1812.00332)), MobileNetV3 ([Tan et al., 2019](http://proceedings.mlr.press/v97/tan19a.html)), EfficientNet ([Howard et al., 2019](http://openaccess.thecvf.com/content_ICCV_2019/html/Howard_Searching_for_MobileNetV3_ICCV_2019_paper.html)). [He et al., 2021](https://arxiv.org/pdf/1908.00709.pdf) also provide a useful survey for recent advances. \n\n4. **Comparisons**: Two really important related papers that I believe merit a in-depth discussion:\n   1. _[Deconstructing Lottery Tickets](https://arxiv.org/abs/1905.01067)_. They have some interesting results around the significance of the sign of the weights in the context of lottery tickets. \n   2. _Zen-Nas ([Lin et al., 2021](http://openaccess.thecvf.com/content/ICCV2021/html/Lin_Zen-NAS_A_Zero-Shot_NAS_for_High-Performance_Image_Recognition_ICCV_2021_paper.html))_: Another really important related work to cite and compare against is Zen-NAS. It's an almost identical setup to your problem formulation.\n\n5. **Experiments**: I think there are potentially two more interesting experiments for the authors to run. \n    1. _[NATS-Bench](https://github.com/D-X-Y/NATS-Bench)_: The latest iteration of the NAS-Bench used by the authors. \n    2. _ImageNet_: I think having one full-scale ImageNet experiment will be very powerful. The authors could even follow the setup of the Zen-NAS paper in order to potentially save on compute cost and recycle the results reported in that paper. \n\n### Ways to improve my score\n\nI do hope the authors decide to engage during the rebuttal period. I think the method has potential and hopefully, the authors can address the raised issues during that time. \n\n--- \n\n### Update after the rebuttal \n\nThe authors engaged very productively with my feedback during the rebuttal and have addressed my concerns. The paper clearly meets the acceptance threshold now in my opinion. I am raising my overall score from 6 to 8 and \"technical novelty\" from 2 to 3. ", "summary_of_the_paper": "The paper proposes a new evaluation metric for scoring untrained, randomly initialized neural network architectures (zero-shot NAS) in order to predict their accuracy/performance after training. The score is based on evaluating the gradient signs and is shown to outperform existing approaches on NAS benchmarks (NAS-Bench 101, 201, NDS).", "summary_of_the_review": "The paper proposes an interesting and sound idea but currently falls short of properly contextualizing their work within existing work and consequently comparing against recent work experimentally as well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is focussed on proposing a new evaluation metric for evaluating untrained, randomly initialized neural network architectures towards predicting their accuracy/performance after training. The metric they propose is based on evaluating the gradient sign. The method shown to outperform existing approaches on NAS benchmarks.

The reviewers found the paper's idea simple but effective. The experimental evaluation and efficacy of the proposed method were the main strong points of the paper. The paper was also significantly improved during the discussion period both in terms of presentation and the scope of experiments/comparisons was enlarged. 

While the metric is theoretically motivated, I personally found some of the theoretical statements weak in terms of assumptions/clarity. I would request the authors to consider taking this and other suggestions made by reviewers into account 

Overall I recommend acceptance based on the strong and thorough experimental results shown by the paper on a problem of clear interest to the community.
Decision: Accept (Poster)