  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 {\Psi} 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 {\Psi} under
reasonable assumptions. In addition, we design GradSign, an accurate and simple
approximation of {\Psi} 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 {\rho} 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.
