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

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

Abstract

Neural Architecture Search (NAS) has significantly advanced automated network design, but its efficiency is often hampered by the need for extensive model training. We introduce NAS at Initialization (NASI), a training-free algorithm that utilizes the Neural Tangent Kernel (NTK) to characterize architecture performance at the moment of initialization. By leveraging the trace norm of the NTK as a proxy for converged performance, NASI eliminates the training loop entirely. Our method is shown to be both label- and data-agnostic, achieving competitive results on CIFAR and ImageNet benchmarks with a 100x speedup over traditional methods.

Introduction

Designing high-performance neural networks manually is a labor-intensive process. Neural Architecture Search (NAS) aims to automate this, yet early iterations were computationally prohibitive, requiring thousands of GPU hours to train candidate models. Even modern "one-shot" methods like DARTS require significant labeled data and compute. NASI addresses this by asking: can we identify the best architecture before training even begins? By bridging theoretical deep learning with practical search, NASI finds state-of-the-art architectures in minutes.

Methodology: The NTK Proxy

The core of NASI lies in the Neural Tangent Kernel (NTK). The NTK describes the evolution of a network's outputs during gradient descent. The authors demonstrate that the trace norm of the NTK at initialization provides a theoretical upper bound on training loss. A higher trace norm indicates greater representation power and faster convergence potential. To ensure stability, NASI incorporates a complexity penalty, preventing the search from selecting unstable, un-trainable structures.

To make this practical, the full NTK calculation—which is normally expensive—is approximated using the Frobenius norm of the Jacobian matrix. This allows the evaluation to be performed on a single mini-batch of data using standard automatic differentiation tools.

Label- and Data-Agnosticism

A remarkable finding of this research is that the search process is largely independent of the specific data or labels used. Because the NTK is a property of the network's structure and the input distribution, the relative ranking of architectures remains stable even under extreme conditions.

Correlation of the NTK-based proxy using random data

As illustrated in the figures above, the proxy maintains a near-perfect correlation ($\rho = 1.00$) with performance when using random Gaussian noise instead of real images (Figure 3) or random labels (Figure 6). This "agnostic" property suggests that the geometric properties of the architecture at initialization are the primary drivers of its eventual success.

Experimental Results

NASI was evaluated on standard benchmarks including CIFAR-10, CIFAR-100, and ImageNet. The results highlight a massive leap in efficiency:

  • Efficiency: On the DARTS search space, NASI completes its search in just 0.24 GPU hours (roughly 15 minutes), a 100x speedup over the original DARTS algorithm.
  • Accuracy: On CIFAR-10, NASI achieved a test error of 2.79%, competitive with training-intensive methods.
  • Transferability: Architectures found on CIFAR-10 transferred effectively to ImageNet, reaching a top-1 error of 24.3%, outperforming many human-designed efficient models.

Conclusion

NASI represents a significant step toward making NAS accessible and efficient. By moving the search to the initialization phase and leveraging the NTK, it removes the bottleneck of model training. Its label- and data-agnostic nature further simplifies the search process, allowing for the discovery of robust architectures without the need for curated datasets. Future work may extend these initialization-based proxies to more complex domains like object detection and large-scale language modeling.

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 converged 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