When Training-Free Nas Meets Vision Transformers: A Neural Tangent Kernel Perspective

Qiqi Zhou, Yichen ZhuICASSP 2024 · OpenReview

TL;DR

This paper tackles the challenge of efficiently searching for optimal Vision Transformer (ViT) architectures without costly training. They discover that traditional Neural Tangent Kernel (NTK) methods, effective for CNNs, fail for ViTs because they primarily capture low-frequency signal learning, while ViTs also rely on high-frequency features. To overcome this, they introduce ViNTK, a novel approach that incorporates Fourier features to account for high-frequency signals, significantly accelerating ViT architecture search.

What Problem Does This Paper Address?

Neural Architecture Search (NAS) aims to automate the design of high-performing neural networks. While traditional NAS methods require extensive training, "training-free" NAS methods use performance predictors at initialization to speed up the search. These predictors, often based on the Neural Tangent Kernel (NTK), have shown promise for Convolutional Neural Networks (CNNs). However, Vision Transformers (ViTs), with their distinct self-attention mechanisms and feed-forward networks, present a new challenge. This paper investigates why existing NTK-based training-free metrics are ineffective for searching ViT architectures and proposes a solution to make this process efficient and reliable.

Methods

The core of the paper lies in understanding and addressing the limitations of NTK for ViTs.

  • NTK's Low-Frequency Bias: The authors hypothesize and theoretically demonstrate that NTK metrics are strongly correlated with a network's ability to learn low-frequency signals. This is problematic for ViTs, as their self-attention mechanisms act as low-pass filters (capturing low frequencies), but they also leverage high-frequency signals for accurate image discrimination. This mismatch causes NTK to misjudge ViT performance.
  • ViNTK: Fourier Neural Tangent Kernel: To bridge this gap, they introduce ViNTK. This method extends the standard NTK by integrating Fourier features from the input data. This integration allows ViNTK to capture and evaluate the network's capacity to learn both low- and high-frequency signals, providing a more comprehensive performance prediction for ViTs. The authors leverage random Fourier features to approximate the Fourier transform efficiently.

Datasets

The paper evaluates its proposed method on standard computer vision benchmarks:

  • Image Classification: ImageNet-1K
  • Semantic Segmentation: Cityscapes and ADE20K

The authors also utilize several ViT-specific search spaces, including the AutoFormer search space and the NASViT search space, to test their method's effectiveness across different architectural configurations.

Key Insights and Ideas

  • NTK's "Blind Spot" for ViTs: The most significant insight is that NTK, while effective for CNNs, fundamentally struggles with ViTs because it overlooks the crucial role of high-frequency signal processing in ViT's architecture. This explains the poor correlation observed between NTK metrics and actual ViT performance.
  • ViT's Dual Nature: ViTs are shown to have a dual nature in feature learning: self-attention filters low frequencies, but the overall architecture still relies on high frequencies for discrimination. This duality is the root cause of NTK's inefficacy.
  • Fourier Features as a Solution: Incorporating Fourier features into NTK (ViNTK) is a clever way to explicitly account for the high-frequency components that NTK misses, thereby creating a more accurate predictor for ViT architectures.
  • Focusing on MSAs: Experiments isolating the Multi-Head Self-Attention (MSA) modules reveal that NTK can be effective when only low-frequency components are considered, reinforcing the hypothesis about NTK's low-frequency bias.

Key Results

  • Improved Correlation: ViNTK shows significantly stronger correlations (Kendall-Tau values) between its predictions and actual ViT performance compared to standard NTK-based metrics on various ViT search spaces.
  • Accelerated Search: ViNTK drastically reduces the search cost for ViT architectures. For instance, in the NASViT search space, ViNTK achieves a search cost that is 1/27th of traditional methods like NASViT, while maintaining similar or slightly better performance.
  • Competitive Performance: Architectures found using ViNTK achieve comparable or superior accuracy on ImageNet-1K classification and competitive performance on semantic segmentation tasks (Cityscapes, ADE20K) compared to state-of-the-art NAS methods.

Limitations and Future Work

  • Computational Cost of Fourier Features: While the paper states the extra computational cost of ViNTK is negligible, the theoretical integration of Fourier features can add complexity. The practical implementation's efficiency is a key advantage.
  • Generalizability to Other Architectures: The paper focuses on ViTs. Future work could explore if ViNTK or similar Fourier-enhanced NTK methods can improve NAS for other novel architectures that might also have complex feature learning characteristics.
  • Further Theoretical Analysis: While the paper provides theoretical justification for NTK's bias, deeper theoretical explorations into the interaction of Fourier features and NTK for diverse network components could be beneficial.

Summary updated

Abstract

This paper investigates the Neural Tangent Kernel (NTK) to search vision transformers without training. In contrast with the previous observation that NTK-based metrics can effectively predict CNN’s performance at initialization, we empirically show their inefficacy in the ViT search space. We hypothesize that the fundamental feature learning preference within ViT contributes to the ineffectiveness of applying NTK to NAS for ViT. We both theoretically and empirically validate that NTK essentially estimates the ability of neural networks that learn low-frequency signals, completely ignoring the impact of high-frequency signals in feature learning. To address this limitation, we propose a new method called ViNTK that generalizes the standard NTK to the high-frequency domain by integrating the Fourier features from inputs. Experiments with multiple ViT search spaces on image classification and semantic segmentation tasks show that our method can significantly speed up search costs over prior state-of-the-art NAS for ViT while maintaining similar performance on searched architectures.
BibTeX
@inproceedings{zhou2024when,
  author = {Qiqi Zhou and Yichen Zhu},
  title = {{When Training-Free Nas Meets Vision Transformers: A Neural Tangent Kernel Perspective}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=5k5AvSXpuU},
}
Figure