SNAS: STOCHASTIC NEURAL ARCHITECTURE SEARCH
We propose Stochastic Neural Architecture Search (SNAS), an economical endto-end solution to Neural Architecture Search (NAS) that trains neural operation parameters and architecture distribution parameters in same round of backpropagation, while maintaining the completeness and differentiability of the NAS pipeline. In this work, NAS is reformulated as an optimization problem on parameters of a joint distribution for the search space in a cell. To leverage the gradient information in generic differentiable loss for architecture search, a novel search gradient is proposed. We prove that this search gradient optimizes the same objective as reinforcement-learning-based NAS, but assigns credits to structural decisions more efficiently. This credit assignment is further augmented with locally decomposable reward to enforce a resource-efficient constraint. In experiments on CIFAR-10, SNAS takes fewer epochs to find a cell architecture with state-of-theart accuracy than non-differentiable evolution-based and reinforcement-learningbased NAS, which is also transferable to ImageNet. It is also shown that child networks of SNAS can maintain the validation accuracy in searching, with which attention-based NAS requires parameter retraining to compete, exhibiting potentials to stride towards efficient NAS on big datasets.
Summary:
This paper proposes Stochastic Neural Architecture Search (SNAS), a method to automatically and efficiently search for neural architectures. It is built upon 2 existing works on these topics, namely ENAS (Pham et al 2018) and DARTS (Liu et al 2018).
SNAS provides nice theory and explanation of gradient computations, unites the strengths and avoid the weaknesses of ENAS and DARTS. There are many details in the paper, including the Appendix. The idea is as follows:
+------------+---------------------+-------------------------+
| Method | Differentiable | Directly Optimize |
|                |                           |    NAS reward       |
+------------+---------------------+-------------------------+
| ENAS     |      No                |        Yes                   |
| DARTS   |      Yes               |        No                    |
| SNAS     |      Yes               |        Yes                   |
+------------+---------------------+-------------------------+
SNAS inherits the idea of ENAS and DARTS by superpositioning all possible architectures into a Directed Acyclic Graph (DAG), effectively sharing the weights among all architectures. However, SNAS improves over ENAS and DARTS as follows (Section 2.2):
1. SNAS improves over ENAS in that it allows independent sampling at edges in the shared DAG, leading to a more tractable gradient at the edges of the DAG, which in turn allows more tractable Monte Carlo estimation of the gradients with respect to the architectural parameters.
2. While DARTS also has the property (1), DARTS implements this by computing the expected value at each node in the DAG, with respect to the joint distribution of the input edges and the operations. This makes DARTS not optimize the direct NAS objective. SNAS, due to their smart manipulation of architectural gradients using Gumbel variables, still optimizes the same objective with NAS and ENAS, but has a smoother gradients.
Experimental results in the paper show that SNAS finds architectures on CIFAR-10 that are comparable to those found by ENAS and DARTS, using a reasonable amount of computing resource. These architectures can also be transferred to learn competent models on ImageNet, like those of DARTS. Furthermore, experimental observations (Figure 3) are consistent with the theory above, that is:
1. The search process of SNAS is more stable than that of ENAS (as SNAS samples with a smaller variance).
2. Architectures found by SNAS perform better than those of DARTS, as SNAS searches directly for the NAS reward of the sampled models. 
Strengths:
1. SNAS unites the strengths and avoids the weaknesses of ENAS and DARTS
2. SNAS provides a nice theory, which is verified through their experimental results.
Weaknesses:
I don’t really have any complaints about this paper. Some presentations of the paper might have been improved, e.g. the discussion on the ZERO operation in other comments should have been included.