  Neural architecture search (NAS) aims to produce the optimal sparse solution
from a high-dimensional space spanned by all candidate connections. Current
gradient-based NAS methods commonly ignore the constraint of sparsity in the
search phase, but project the optimized solution onto a sparse one by
post-processing. As a result, the dense super-net for search is inefficient to
train and has a gap with the projected architecture for evaluation. In this
paper, we formulate neural architecture search as a sparse coding problem. We
perform the differentiable search on a compressed lower-dimensional space that
has the same validation loss as the original sparse solution space, and recover
an architecture by solving the sparse coding problem. The differentiable search
and architecture recovery are optimized in an alternate manner. By doing so,
our network for search at each update satisfies the sparsity constraint and is
efficient to train. In order to also eliminate the depth and width gap between
the network in search and the target-net in evaluation, we further propose a
method to search and evaluate in one stage under the target-net settings. When
training finishes, architecture variables are absorbed into network weights.
Thus we get the searched architecture and optimized parameters in a single run.
In experiments, our two-stage method on CIFAR-10 requires only 0.05 GPU-day for
search. Our one-stage method produces state-of-the-art performances on both
CIFAR-10 and ImageNet at the cost of only evaluation time.
