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

Neural Architecture Search (NAS) has been explosively studied to automate the\ndiscovery of top-performer neural networks. Current works require heavy\ntraining of supernet or intensive architecture evaluations, thus suffering from\nheavy resource consumption and often incurring search bias due to truncated\ntraining or approximations. Can we select the best neural architectures without\ninvolving any training and eliminate a drastic portion of the search cost? We\nprovide an affirmative answer, by proposing a novel framework called\ntraining-free neural architecture search (TE-NAS). TE-NAS ranks architectures\nby analyzing the spectrum of the neural tangent kernel (NTK) and the number of\nlinear regions in the input space. Both are motivated by recent theory advances\nin deep networks and can be computed without any training and any label. We\nshow that: (1) these two measurements imply the trainability and expressivity\nof a neural network; (2) they strongly correlate with the network's test\naccuracy. Further on, we design a pruning-based NAS mechanism to achieve a more\nflexible and superior trade-off between the trainability and expressivity\nduring the search. In NAS-Bench-201 and DARTS search spaces, TE-NAS completes\nhigh-quality search but only costs 0.5 and 4 GPU hours with one 1080Ti on\nCIFAR-10 and ImageNet, respectively. We hope our work inspires more attempts in\nbridging the theoretical findings of deep networks and practical impacts in\nreal NAS applications. Code is available at:\nhttps://github.com/VITA-Group/TENAS.\n