Source-linked AI summary
Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective
Wuyang Chen, Xinyu Gong, Zhangyang Wang
TL;DR
NAS seeks efficient, reliable architecture evaluation and optimization, but existing approaches incur heavy search costs and can introduce bias. TE-NAS ranks architectures without training or labels using NTK and linear-region indicators, achieving competitive results with very short searches.
Problem
NAS architecture evaluation and optimization remain difficult because existing methods incur heavy evaluation costs and can suffer search bias from approximations.
Method
TE-NAS ranks architectures using NTK condition-number or spectrum measurements and linear-region counts, then applies pruning-based search without training or labels.
Results
TE-NAS achieves competitive NAS performance, including 24.5%/7.5% top-1/5 test error on ImageNet with four GPU hours on one 1080Ti.
Takeaways & Limitations
Training-free theoretical indicators can support practical architecture ranking while reducing search time and separating trainability from expressivity.
Takeaways & Limitations
Predictor-based NAS may require training 2,000 to 50,000 architectures, while TE-NAS's search-space setting includes different single-path criteria for NAS-Bench-201 and DARTS.
Abstract
from arXiv · showhide
Neural Architecture Search (NAS) has been explosively studied to automate the discovery of top-performer neural networks. Current works require heavy training of supernet or intensive architecture evaluations, thus suffering from heavy resource consumption and often incurring search bias due to truncated training or approximations. Can we select the best neural architectures without involving any training and eliminate a drastic portion of the search cost? We provide an affirmative answer, by proposing a novel framework called training-free neural architecture search (TE-NAS). TE-NAS ranks architectures by analyzing the spectrum of the neural tangent kernel (NTK) and the number of linear regions in the input space. Both are motivated by recent theory advances in deep networks and can be computed without any training and any label. We show that: (1) these two measurements imply the trainability and expressivity of a neural network; (2) they strongly correlate with the network's test accuracy. Further on, we design a pruning-based NAS mechanism to achieve a more flexible and superior trade-off between the trainability and expressivity during the search. In NAS-Bench-201 and DARTS search spaces, TE-NAS completes high-quality search but only costs 0.5 and 4 GPU hours with one 1080Ti on CIFAR-10 and ImageNet, respectively. We hope our work inspires more attempts in bridging the theoretical findings of deep networks and practical impacts in real NAS applications. Code is available at: https://github.com/VITA-Group/TENAS.
1 INTRODUCTION
NAS automates architecture discovery but faces high-dimensional evaluation and optimization challenges, costly searches, and bias from truncated training. TE-NAS addresses these issues by ranking architectures using training-free, label-free indicators of trainability and expressivity.
- Manual architecture design is time- and resource-intensive and depends on expertise that may not scale.
- NAS must determine both how to evaluate architectures and how to optimize the resulting objective in high-dimensional search spaces.
- Truncated training and early stopping accelerate NAS but can bias architecture rankings because their results are inaccurate.
- NAS asks whether architectures can be optimized at initialization without training and evaluated through their trainability and expressivity.
- TE-NAS uses NTK condition-number or spectrum measurements and linear-region counts to characterize trainability and expressivity without training or labels.
- TE-NAS adds pruning-based search to trade off trainability and expressivity while reducing search cost.
2 RELATED WORKS
Prior NAS methods reduce direct training through predictors or training-free proxies, but often retain costly data collection or limited explanations. TE-NAS connects theoretically motivated network properties with architecture ranking and search.
- Weight-sharing and single-path NAS methods generally suffer from heavy architecture-search costs.
- Predictor-based NAS estimates architecture accuracy or ranking instead of directly training every candidate.
- Predictor-based methods may require training 2,000 to 50,000 sampled architectures and repeating predictor construction for unseen search spaces.
- Training-free Jacobian-based NAS shares the initialization-search motivation but leaves its mechanism insufficiently explained and its NAS-Bench-201 performance behind state-of-the-art methods.
- Deep-learning theory motivates NTK-based trainability analysis and linear-region measures of ReLU-network expressivity.
- TE-NAS uses these theoretically motivated indicators to rank architectures and bridge deep-network theory with practical NAS applications.
3 METHODS
TE-NAS evaluates architectures without training or labels by combining NTK conditioning for trainability with linear-region counts for expressivity, then searches through pruning. These indicators correlate with test accuracy and guide a trajectory that first improves trainability before preserving expressivity.
- Trainability by NTK condition number: The NTK condition number κN measures trainability: larger values indicate poorer trainability, and κN is computed without gradient descent or labels.Its basis is the eigenvalue ratio κ = λ0/λm; divergent κ makes a network untrainable.
- Trainability by NTK condition number: κN negatively correlates with NAS-Bench201 test accuracy, with Kendall-tau correlation −0.42.Minimizing κN during search therefore favors architectures with higher reported performance.
- Expressivity by number of linear regions: The number of linear regions measures ReLU-network expressivity by counting distinct input-space activation-pattern regions.The approximation averages measurements from parameters sampled with Kaiming Norm Initialization.
- Expressivity by number of linear regions: The number of linear regions positively correlates with NAS-Bench201 test accuracy, with Kendall-tau correlation 0.5.Maximizing this quantity during search favors architectures with higher reported performance.
- Combining trainability and expressivity: κN and the linear-region count prefer different operators: both favor conv3 × 3, while linear regions favor conv1 × 1 and κN favors skip-connect.Their complementary preferences motivate combining trainability and expressivity rather than optimizing either indicator alone.
- Pruning-by-importance architecture search: TE-NAS sums the relative rankings of κN and linear-region count, then prunes one operator per edge in each outer-loop round until a single-path network remains.The pruning trajectory first reduces κN to improve trainability, then fine-tunes the architecture while limiting expressivity loss.
4 EXPERIMENTS
TE-NAS is evaluated on NAS-Bench-201 and DARTS search spaces, achieving strong accuracy while substantially reducing search cost on CIFAR-10 and ImageNet.
- Evaluation settings: TE-NAS is evaluated on NAS-Bench-201 and DARTS search spaces using comparisons with state-of-the-art NAS methods.NAS-Bench-201 contains 15,625 architectures and supports CIFAR-10, CIFAR-100, and ImageNet-16-120.
- NAS-Bench-201 results: 5× ∼19× reduction in search cost accompanies the best accuracy on all three NAS-Bench-201 datasets.The result is reported as the mean and standard deviation across four independent runs with different random seeds.
- DARTS CIFAR-10 results: 2.63% test error is achieved on CIFAR-10 while reducing search cost to only 0.05 GPU-day.ProxylessNAS obtains lower test error but uses a different search space, longer search time, and a larger model size.
- DARTS ImageNet results: 24.5%/7.5% top-1/5 test error is achieved on ImageNet in the mobile setting with four GPU hours on one GTX 1080Ti.The ImageNet search takes longer than CIFAR-10 because of the larger input size and more network parameters.
5 CONCLUSION
The conclusion presents TE-NAS as a training-free approach that uses theoretically inspired indicators to address NAS evaluation and optimization while reducing search time.
- Conclusion: NAS must address what constitutes a good architecture and how to find it, while validation accuracy alone has search bias and heavy evaluation cost.These are identified as the two key questions in NAS.
- Conclusion: The NTK spectrum and number of linear regions correlate strongly with network performance and separately analyze trainability and expressivity.The indicators are used without involving training.
- Conclusion: TE-NAS achieves competitive NAS performance with minimum search time without involving training.The work frames this as a bridge between theoretical findings about deep networks and practical NAS applications.
A IMPLEMENTATION DETAILS
The implementation measures NTK- and activation-based indicators at randomly initialized, fixed network weights, then retrains the searched architectures using established optimization settings.
- Indicator computation: κN uses one training mini-batch of size 32, while ˆRN uses 5,000 images to collect activation patterns from all ReLU layers.The two calculations are repeated three times in the experiments.
- Indicator computation: The network weights are randomly drawn from Kaiming Normal initialization and remain fixed, so indicator computation involves no training.This procedure is repeated for each of the three calculations.
- Retraining: After search, CIFAR-10 retraining uses cutout, drop-path probability 0.3, and an auxiliary tower weight of 0.4, while ImageNet also uses label smoothing.Both settings use SGD with cosine annealing.
B SEARCHED ARCHITECTURE
TE-NAS searches normal and reduction cells directly on CIFAR-10 and ImageNet, while analyzing how cell depth and width affect trainability and expressivity in the DARTS search space.
- B SEARCHED ARCHITECTURE: TE-NAS directly searches normal and reduction cells on CIFAR-10 and ImageNet.
- B SEARCHED ARCHITECTURE: Figures 6 and 7 visualize the normal and reduction cells discovered on CIFAR-10 and ImageNet, respectively.
- B SEARCHED ARCHITECTURE: In DARTS, cell depth is the longest input-to-output connection path, while cell width sums intermediate-node edges connected to input nodes.
- B SEARCHED ARCHITECTURE: Shallow but wide cells are preferred by both κN and ˆRN for trainability and expressivity.
D.1 SEARCH WITH ONLY κN OR ˆRN
Using only κN or ˆRN produces inferior search performance, whereas TE-NAS performs best among the tested combination and pruning strategies.
- D.1 SEARCH WITH ONLY κN OR ˆRN: Using only κN or ˆRN leads to inferior performance, showing that search should maintain both trainability and expressivity.
- D.1 SEARCH WITH ONLY κN OR ˆRN: The alternatives include pruning by the minimum, maximum, or summed numerical changes of the two indicators.
- D.1 SEARCH WITH ONLY κN OR ˆRN: TE-NAS outperforms the considered alternatives, indicating that balancing κN and ˆRN and ranking changes is important.
D.3 CORRELATION BETWEEN TEST ACCURACY AND COMBINATION OF κN AND ˆRN
Combining the rankings of κN and ˆRN produces a stronger correlation with architecture test accuracy than either indicator’s ranking alone.
- D.3 CORRELATION BETWEEN TEST ACCURACY AND COMBINATION OF κN AND ˆRN: The combined metric from summing κN and ˆRN rankings achieves much higher correlation with test accuracy.
- D.3 CORRELATION BETWEEN TEST ACCURACY AND COMBINATION OF κN AND ˆRN: The two indicators prefer different operators for trainability and expressivity, so their combination filters architectures that are poor in either aspect.
E GENERALIZATION V.S. TEST ACCURACY
κN and RN characterize trainability and expressivity during training, but they do not directly measure the generalization gap or test accuracy. In NAS-Bench201, strong training–test accuracy correlation helps explain their useful test-accuracy search results.
- E GENERALIZATION V.S. TEST ACCURACY: The generalization gap is the difference between performance on training data and unseen data from the same distribution.
- E GENERALIZATION V.S. TEST ACCURACY: κN and RN indicate how well a network fits training data but do not directly indicate its generalization gap or test accuracy.
- E GENERALIZATION V.S. TEST ACCURACY: In NAS-Bench201, training accuracy strongly correlates with test accuracy, possibly because the standard search space implicitly excludes severe overfitting.
- E GENERALIZATION V.S. TEST ACCURACY: The training–test correlation helps explain why initialization-based κN and RN can still achieve good test-accuracy search results.