  This paper introduces a novel optimization method for differential neural
architecture search, based on the theory of prediction with expert advice. Its
optimization criterion is well fitted for an architecture-selection, i.e., it
minimizes the regret incurred by a sub-optimal selection of operations. Unlike
previous search relaxations, that require hard pruning of architectures, our
method is designed to dynamically wipe out inferior architectures and enhance
superior ones. It achieves an optimal worst-case regret bound and suggests the
use of multiple learning-rates, based on the amount of information carried by
the backward gradients. Experiments show that our algorithm achieves a strong
performance over several image classification datasets. Specifically, it
obtains an error rate of 1.6% for CIFAR-10, 24% for ImageNet under mobile
settings, and achieves state-of-the-art results on three additional datasets.
