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.

翻译：神经结构搜索 (NAS) 已经进行了爆炸性研究, 以自动发现顶层神经网络。 当前的工程需要大量培训超级网络或密集的建筑评估, 从而导致资源消耗过重, 并且由于短短的培训或近似而经常引起搜索偏差。 我们能否选择最佳的神经结构, 而不进行任何培训, 并消除搜索成本的极大一部分? 我们提供一个肯定的答案, 方法是提出一个叫作无培训神经结构搜索(TE-NAS)的新框架 。 TE-NAS 通过分析神经透视( NTK) 的频谱和输入空间中的线性区域数量, 这两项工程都受到深层网络理论进步的驱动, 并且可以不经任何培训和标签而进行计算 。 我们表明:(1) 这两项测量意味着神经网络的可培训和表达性; (2) 它们与网络的测试准确性密切相关。 此外, 我们设计了一个基于运行基础的NAS 实际激励机制, 以便在搜索过程中实现更灵活和更高级的培训和表达性交易。 在 NAS- 10- AS 的深度网络中, 我们的深度搜索空间和 DAR- 10 搜索空间中, 我们的搜索空间中, 我们只有1 高的搜索空间和DAR- 。