# Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective

arXiv: https://arxiv.org/abs/2102.11535 · HTML: https://mlsanity.com/paper/2102.11535/

## Key facts

- Cited by 169 papers in the map (data through 14 Oct 2026).
- Builds on 61 of its 71 references that are in the map.
- First posted on arXiv 23 Feb 2021.

## Builds on (most cited first, 30 of 61)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [EfficientDet: Scalable and Efficient Object Detection](https://mlsanity.com/paper/1911.09070/) (2019)
- [MnasNet: Platform-Aware Neural Architecture Search for Mobile](https://mlsanity.com/paper/1807.11626/) (2018)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware](https://mlsanity.com/paper/1812.00332/) (2018)
- [Progressive Neural Architecture Search](https://mlsanity.com/paper/1712.00559/) (2017)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Single Path One-Shot Neural Architecture Search with Uniform Sampling](https://mlsanity.com/paper/1904.00420/) (2019)
- [A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets](https://mlsanity.com/paper/1707.08819/) (2017)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://mlsanity.com/paper/1907.05737/) (2019)
- [Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmentation](https://mlsanity.com/paper/1901.02985/) (2019)
- [Searching for A Robust Neural Architecture in Four GPU Hours](https://mlsanity.com/paper/1910.04465/) (2019)
- [Random Search and Reproducibility for Neural Architecture Search](https://mlsanity.com/paper/1902.07638/) (2019)
- [Neural Architecture Search without Training](https://mlsanity.com/paper/2006.04647/) (2020)
- [Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation](https://mlsanity.com/paper/1904.12760/) (2019)
- [SMASH: One-Shot Model Architecture Search through HyperNetworks](https://mlsanity.com/paper/1708.05344/) (2017)

## Built on by (most cited first, 30 of 169)

- [When Vision Transformers Outperform ResNets without Pre-training or Strong Data Augmentations](https://mlsanity.com/paper/2106.01548/) (2021)
- [Sustainable AI: Environmental Implications, Challenges and Opportunities](https://mlsanity.com/paper/2111.00364/) (2021)
- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [Neural Architecture Search: Insights from 1000 Papers](https://mlsanity.com/paper/2301.08727/) (2023)
- [Deep Model Reassembly](https://mlsanity.com/paper/2210.17409/) (2022)
- [Representation Topology Divergence: A Method for Comparing Neural Network Representations](https://mlsanity.com/paper/2201.00058/) (2021)
- [Fast Finite Width Neural Tangent Kernel](https://mlsanity.com/paper/2206.08720/) (2022)
- [ZiCo: Zero-shot NAS via Inverse Coefficient of Variation on Gradients](https://mlsanity.com/paper/2301.11300/) (2023)
- [Neural Architecture Search for Spiking Neural Networks](https://mlsanity.com/paper/2201.10355/) (2022)
- [A Survey on Green Deep Learning](https://mlsanity.com/paper/2111.05193/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies](https://mlsanity.com/paper/2210.03230/) (2022)
- [Graph-DETR3D: Rethinking Overlapping Regions for Multi-View 3D Object Detection](https://mlsanity.com/paper/2204.11582/) (2022)
- [KNAS: Green Neural Architecture Search](https://mlsanity.com/paper/2111.13293/) (2021)
- [Training-free Transformer Architecture Search](https://mlsanity.com/paper/2203.12217/) (2022)
- [NAS-Bench-360: Benchmarking Neural Architecture Search on Diverse Tasks](https://mlsanity.com/paper/2110.05668/) (2021)
- [Deep Active Learning by Leveraging Training Dynamics](https://mlsanity.com/paper/2110.08611/) (2021)
- [SplineCam: Exact Visualization and Characterization of Deep Network Geometry and Decision Boundaries](https://mlsanity.com/paper/2302.12828/) (2023)
- [NTK-SAP: Improving neural network pruning by aligning training dynamics](https://mlsanity.com/paper/2304.02840/) (2023)
- [DisWOT: Student Architecture Search for Distillation WithOut Training](https://mlsanity.com/paper/2303.15678/) (2023)
- [NASI: Label- and Data-agnostic Neural Architecture Search at Initialization](https://mlsanity.com/paper/2109.00817/) (2021)
- [Machine Learning for Microcontroller-Class Hardware: A Review](https://mlsanity.com/paper/2205.14550/) (2022)
- [AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search](https://mlsanity.com/paper/2403.19232/) (2024)
- [Stitchable Neural Networks](https://mlsanity.com/paper/2302.06586/) (2023)
- [Neural Tangent Kernel: A Survey](https://mlsanity.com/paper/2208.13614/) (2022)
- [LEMON: Lossless model expansion](https://mlsanity.com/paper/2310.07999/) (2023)
- [ProxyBO: Accelerating Neural Architecture Search via Bayesian Optimization with Zero-cost Proxies](https://mlsanity.com/paper/2110.10423/) (2021)
- [Global Convergence of MAML and Theory-Inspired Neural Architecture Search for Few-Shot Learning](https://mlsanity.com/paper/2203.09137/) (2022)
- [Joint Neural Architecture and Hyperparameter Search for Correlated Time Series Forecasting](https://mlsanity.com/paper/2211.16126/) (2022)
- [What Can the Neural Tangent Kernel Tell Us About Adversarial Robustness?](https://mlsanity.com/paper/2210.05577/) (2022)

## Abstract (arXiv)

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.