  Neural architecture search (NAS) is an approach for automatically designing a
neural network architecture without human effort or expert knowledge. However,
the high computational cost of NAS limits its use in commercial applications.
Two recent NAS paradigms, namely one-shot and sparse propagation, which reduce
the time and space complexities, respectively, provide clues for solving this
problem. In this paper, we propose a novel search strategy for one-shot and
sparse propagation NAS, namely AdvantageNAS, which further reduces the time
complexity of NAS by reducing the number of search iterations. AdvantageNAS is
a gradient-based approach that improves the search efficiency by introducing
credit assignment in gradient estimation for architecture updates. Experiments
on the NAS-Bench-201 and PTB dataset show that AdvantageNAS discovers an
architecture with higher performance under a limited time budget compared to
existing sparse propagation NAS. To further reveal the reliabilities of
AdvantageNAS, we investigate it theoretically and find that it monotonically
improves the expected loss and thus converges.
