KNAS: Green Neural Architecture Search

Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, Hongxia Yang

Introduction

Neural Architecture Search (NAS) has revolutionized the design of deep learning models by automating the discovery of high-performing architectures. However, this progress comes at a massive environmental and computational cost. Traditional NAS relies heavily on a "train-then-test" paradigm: to evaluate whether an architecture is effective, it must be trained, which consumes enormous computational power. For context, a single NAS search can emit as much carbon as five cars over their entire lifetimes.

While some "fast" NAS methods exist—such as weight-sharing or early stopping—they often suffer from "performance collapse," where the search process converges on poor architectures, or they still require substantial training time. To address this, the authors of KNAS (Green Neural Architecture Search) ask a bold question: Can we evaluate an architecture's potential without training it at all?

The Gradient Kernel Hypothesis

KNAS introduces a training-free approach to finding optimal deep learning models based on the Gradient Kernel Hypothesis. The authors argue that the gradients induced by a network's architecture at random initialization are the most direct factor deciding its eventual convergence and generalization capabilities.

To quantify this potential, they identify a key feature: the Gram matrix of gradients (GM).

  1. Theoretical Foundation: The authors prove that the Frobenius norm (F-norm) of the GM provides an upper bound on the convergence rate. Essentially, a higher GM score suggests a "healthier" gradient flow.
  2. The Metric (MGM): They utilize the Mean of the Gram Matrix (MGM) as a proxy for performance. MGM captures two critical aspects of learning: gradient magnitude (which helps avoid vanishing gradients) and gradient correlation (which ensures updates aren't "ataxic" or conflicting).

The KNAS Algorithm

The resulting search algorithm is remarkably efficient:

  • Randomly sample a set of candidate architectures.
  • Compute the MGM for each candidate using only a few batches of data at initialization—requiring absolutely zero training.
  • Select the top-$k$ candidates with the highest MGM scores.
  • Train only these few selected candidates to determine the final winner.

To make this computationally feasible, KNAS approximates the MGM by sampling a small subset of parameters from each layer rather than computing the entire gradient vector.

Key Insights and Results

The authors evaluated KNAS on several standard benchmarks, including NAS-Bench-201 (CIFAR-10, CIFAR-100, and ImageNet-16-120) and the GLUE Benchmark for NLP (MRPC and RTE datasets).

Gradients as a "Health Index"

The most striking insight from KNAS is that you do not need to watch a model learn to know if it can learn. The architecture itself dictates the quality of the gradients from day one. A high MGM indicates that gradients are large enough to drive learning and move in consistent directions. Conversely, low MGM scores point to "ataxic" gradients that cause conflicted parameter updates, slowing down or entirely preventing convergence.

MGM vs. Accuracy

The authors found a strong Spearman correlation (ranging from 0.53 to 0.56) between their training-free MGM score and actual validation accuracy. As illustrated below, architectures with higher MGM ranks consistently yield higher average validation accuracy.

Scatter and bar plots illustrating the positive correlation between MGM rank and validation accuracy.

Performance and Efficiency

KNAS delivers a rare "win-win" scenario in machine learning research: it is both faster and often more accurate than more complex, resource-intensive search methods.

  • Speed: KNAS achieved speedups of 20x to 100x compared to traditional search-based methods like Reinforcement Learning (RL) or Evolution (REA).
  • Vision Performance: On CIFAR-100, KNAS ($k=5$) reached 71.42% accuracy, outperforming popular differentiable methods like DARTS (67.34%) and GDAS (67.60%) while being significantly cheaper to run.
  • NLP Generalization: KNAS is not limited to computer vision. When applied to text classification, the searched architectures outperformed the strong RoBERTa-large baseline on both MRPC and RTE datasets.
  • Consistency: The correlation between MGM and downstream performance holds steady across different datasets and experimental setups.
Scatter plot showing stable Spearman correlation scores across multiple experiments, demonstrating MGM's consistency.

Limitations and Future Work

While KNAS represents a major step toward "Green AI," there are several areas ripe for future exploration:

  • Coarse-Grained Proxy: MGM is a "coarse-grained" indicator. While it successfully identifies high-potential candidates, it may struggle to distinguish between two very similar, high-performing architectures without the final training step (the top-$k$ selection).
  • Search Space Constraints: The experiments were largely conducted on cell-based search spaces (like NAS-Bench-201). Testing KNAS on more diverse, macro-architectural search spaces remains an open challenge.
  • Approximation Sensitivity: Because the method relies on approximating the gradient vector to save memory, future work could investigate how different parameter sampling strategies affect ranking accuracy.

Ultimately, KNAS proves that we can drastically reduce the carbon footprint of Neural Architecture Search by looking closely at the mathematical properties of a network at initialization, paving the way for more sustainable AI development.

Summary updated

Abstract

Many existing neural architecture search (NAS) solutions rely on downstream training for architecture evaluation, which takes enormous computations. Considering that these computations bring a larg...
BibTeX
@inproceedings{xu2021knas,
  author = {Jingjing Xu and Liang Zhao and Junyang Lin and Rundong Gao and Xu Sun and Hongxia Yang},
  title = {{KNAS: Green Neural Architecture Search}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=HudZhXB4mB},
}
Figure