NASI: Label- and Data-agnostic Neural Architecture Search at Initialization

Yao Shu, Shaofeng Cai, Zhongxiang Dai, Beng Chin Ooi, Bryan Kian Hsiang Low

TL;DR

NASI (Neural Architecture Search at Initialization) is a novel algorithm that selects high-performing neural architectures without training a single model. By leveraging the properties of the Neural Tangent Kernel (NTK), NASI provides a theoretically grounded proxy for performance that is both label- and data-agnostic, reducing search costs from days to minutes.

The Problem: Search Inefficiency in NAS

Neural Architecture Search (NAS) aims to automate the design of deep neural networks, moving away from manual, trial-and-error engineering. However, traditional NAS is notoriously expensive because it typically requires training and evaluating thousands of candidate architectures to see which performs best.

Even "one-shot" NAS methods, which share weights across architectures, still require a significant training phase for a "super-net." This paper addresses the fundamental search inefficiency of NAS by asking a provocative question: Can we identify the best architecture at the very moment of initialization, before any training happens?

Methods: Searching via the Neural Tangent Kernel

The core of NASI is the Neural Tangent Kernel (NTK). In the limit of infinite width, the training dynamics of a neural network are governed by this kernel, which remains constant during training.

  1. Performance Proxy: The authors prove mathematically that the training loss of an architecture can be upper-bounded by a function of the trace norm of its NTK at initialization. Essentially, a larger trace norm correlates with better training potential and representation power.
  2. Efficient Approximation: Calculating the full NTK is computationally prohibitive. To solve this, the authors propose an efficient approximation using the Frobenius norm of the Jacobian matrix. This can be computed quickly via automatic differentiation on just a single mini-batch of data.
  3. Differentiable Search: To navigate the massive space of possible architectures, NASI utilizes a Gumbel-Softmax relaxation. This turns the discrete choice of operations (like choosing between a $3\times3$ convolution or a max pool) into a continuous optimization problem that can be solved efficiently using gradient descent.
  4. Complexity Trade-off: The authors introduce a penalty term and a constraint to balance model complexity with trainability. This prevents the search algorithm from simply picking the largest, most complex model, which might be difficult to optimize in practice.

Key Insights and Ideas

Training is Optional

The most profound insight of NASI is that the "DNA" of a good architecture is visible at initialization. You do not need to see a model learn to know if it can learn well.

Label- and Data-Agnosticism

Because the NTK trace norm depends on the architecture's structure rather than specific data patterns, NASI works even with random labels or random Gaussian noise as input. This means you can find a great architecture for CIFAR-10 without actually using CIFAR-10 data during the search phase.

Label-agnostic performance correlation.
Data-agnostic performance correlation.

As shown in the figures above, the performance proxy exhibits near-perfect correlation ($\rho=1.00$) when comparing true labels to random labels, and exceptionally high correlation ($\rho \approx 0.94-0.95$) when comparing true data to random data across different search spaces.

The Complexity/Trainability Balance

The paper highlights that NAS is essentially a search for a "sweet spot." Models need enough complexity to represent the data accurately but must remain structured enough to be optimized efficiently by gradient descent.

Key Results

  • Massive Speedup: NASI completes its search in approximately 0.24 GPU hours (about 15 minutes) on a single Nvidia 1080Ti. For comparison, traditional RL-based NAS can take up to 48,000 hours, and even the popular DARTS method takes roughly 24 hours.
  • Competitive Accuracy: Despite the extreme speedup, NASI achieves a 2.79% error rate on CIFAR-10, which is comparable to or better than many training-heavy, state-of-the-art methods.
  • Strong Transferability: Architectures found by NASI on CIFAR-10 transferred successfully to ImageNet, achieving a 24.3% Top-1 error, outperforming several human-designed and automatically searched models.

Limitations and Future Work

  • Infinite Width Assumption: The theoretical foundation relies on the "infinite width" regime of neural networks. While it works well in practice for finite networks, bridging the gap between this theory and practical application is an ongoing area of study.
  • Loss Function Focus: The theoretical proofs are primarily derived for Mean Squared Error (MSE) loss. While the authors show it works for Cross-Entropy in practice, a more direct theoretical treatment of classification losses could be beneficial.
  • Search Space Constraints: Like most NAS methods, NASI is still constrained by the predefined search space (e.g., the DARTS cell). Expanding this to more diverse or "macro" architectures remains a challenge for future research.

Summary updated

Abstract

Recent years have witnessed a surging interest in Neural Architecture Search (NAS). Various algorithms have been proposed to improve the search efficiency and effectiveness of NAS, i.e., to reduce the search cost and improve the generalization performance of the selected architectures, respectively. However, the search efficiency of these algorithms is severely limited by the need for model training during the search process. To overcome this limitation, we propose a novel NAS algorithm called NAS at Initialization (NASI) that exploits the capability of a Neural Tangent Kernel in being able to characterize the performance of candidate architectures at initialization, hence allowing model training to be completely avoided to boost the search efficiency. Besides the improved search efficiency, NASI also achieves competitive search effectiveness on various datasets like CIFAR-10/100 and ImageNet. Further, NASI is shown to be label- and data-agnostic under mild conditions, which guarantees the transferability of architectures selected by our NASI over different datasets.
BibTeX
@inproceedings{shu2022nasi,
  author = {Yao Shu and Shaofeng Cai and Zhongxiang Dai and Beng Chin Ooi and Bryan Kian Hsiang Low},
  title = {{NASI: Label- and Data-agnostic Neural Architecture Search at Initialization}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=v-v1cpNNK_v},
}
Figure