One-Shot Neural Architecture Search via Compressive Sensing
Authors: Minsu Cho
Mohammadreza Soltani
Chinmay Hegde
Venue:  (2020)
Keywords: deep learning
autoML
neural architecture search
image classification
language modeling

Abstract: Neural architecture search (NAS), or automated design of neural network models, remains a very challenging meta-learning problem. Several recent works (called "one-shot" approaches) have focused on dramatically reducing NAS running time by leveraging proxy models that still provide architectures with competitive performance. In our work, we propose a new meta-learning algorithm that we call CoNAS, or Compressive sensing-based Neural Architecture Search. Our approach merges ideas from one-shot NAS approaches with iterative techniques for learning low-degree sparse Boolean polynomial functions. We validate our approach on several standard test datasets, discover novel architectures hitherto unreported, and achieve competitive (or better) results in both performance and search time compared to existing NAS approaches. Further, we provide theoretical analysis via upper bounds on the number of validation error measurements needed to perform reliable meta-learning; to our knowledge, these analysis tools are novel to the NAS literature and may be of independent interest.

Under review as a conference paper at ICLR 2020
ONE-SHOT NEURAL ARCHITECTURE SEARCH VIA COMPRESSIVE SENSING
Anonymous authors Paper under double-blind review
ABSTRACT
Neural architecture search (NAS), or automated design of neural network models, remains a very challenging meta- meta-learning problem. Several recent works (called "one-shot" approaches) have focused on dramatically reducing NAS running time by leveraging proxy models that still provide architectures with competitive per- formance. In our work, we propose new meta-learning algorithm that we call CoNAS, or Compressive sensing-basee Neural Architecture Search. Our approach merges ideas from one-shot NAS approaches with iterative techniques for learning low-degree sparse Boolean polynomial functions. We validate our approach on several standard test datasets, discover novel architectures hitherto unreported, and achieve competitive (or better) results both performance and search time compared existing NAS approaches. Further, we provide theoretical analysis via upper bounds on the number of validation error measurements needed to perform reliable leta-lleannnn; our knowledge. these analysis tools are novel to the NAS literature and may be of independent interest.
INTRODUCTION
Motivation. Choosing suitable neural network architecture for complex prediction tasks such as image classification and language modeling often requires a substantial effort of trial-and-error. Therefore, there has been a growing interest to automatically learn (or meta-learn) the architecture of neural networks that can achieve competitive (or better) results over hand-designed architectures. The sub-field of neural architecture search (NAS) addresses the problem of designing competitive architectures with small computational budget possible.
Numerous approaches for neural architecture search already exist in the literature, each with their own pros and cons: these include black-box optimization based reinforcement learning (RL) (Zoph & Le, 2017), evolutionary search (Real et al., 2019), and Bayesian optimization (Cao et al., 2019 99; Kandasamy al., 2018 8). Though the algorithmic details vary, most of these NAS methods face the common challenge of evaluating the test/validation performance of a (combinatorially) large number of candidate architecture evaluations.
Our Contributions. In a departure from traditional methods, we approach the NAS problem via the lens of compressive sensing. The field of compressive sensing (or sparse recovery), introduced by the seminal works of (Candes et al., 2006; Donoho et al., 2006), has received significant attention in both ML theory and applications over the last decade, and has influenced the development of numerous advances in nonlinear and combinatorial optimization.
We leverage these advances for the NAS problem. In particular, we develop new NAS method called CoNAS (Compressive sensing-based Neural Architecture Search), which merges ideas from sparse recovery with so-called "one-shot" architecture search methods (Bender al., 2018), described in greater detail below. CoNAS consists of two new innovations: (i) new search space that permits exploration of a large(r) number of diverse candidate architectures, and (ii) a new search strategy that borrows ideas from recovery of Boolean functions from their (sparse) Fourier expansions.
Our experiments show that CoNAS is able to discover a deep convolutional neural network with test error 2.74 + 0.12% on CIFAR-10 classification, outperforming existing state-of-the methods, including DARTs (Liu et al., 2018b), ENAS (Pham et al., 2018), random search with weight-sharing (RSWS) (Li & Talwalkar, 2019), and the baseline vanilla random search method (Liu et al., 201 8b) in

---

Under review as a conference paper at ICLR 2020
terms of test error, search time, model size, and number of multiply-add operations. Moreover, CoNAS can achieve the comparable performance as NASNet (Zoph et al., 2018) and AmoebaNet (Real et al., 2019) with less than one GPU-day of computation. Our experiments networks for language modeling are somewhat short of the state-of-the-art (Zilly et al., 2017), but we find that CoNAS still finds competitive results with less search time than previous NAS approaches. Our results are exactly reproducible (having been trained with fixed pseudorandom seeds), and an implementation of CoNAS will be made publicly available post-peer review.
designing recurrent neural
Finally, while our original motivation was to devise an empirically useful NAS method, a nice benefit is that CoNAS can also be theoretically ana- lyzed, since existing theoretical results for Fourier-sparse Boolean functions can be ported over in order to provide upper bounds for the required num- ber of performance evaluations of sub- architectures of the one-shot model. This, to our knowledge, is one of the first results of their kind in the NAS literature and may be of independent interest. We defer discussion of our approach Section 3.
Stage 1
Stage 2
Sample
mcasurements
Approximate one-shot model (g RS with compressive sensing
Train one-shot model (f)
f)
Restrict f with minimizer of g
Our Techniques. The intuition be- hind compressive sensing is that if signal (or function) can be represented via a sparse basis expansion, then can be recovered (either exactly or ap- proximately) from a small number of randomized measurements. CoNAS leverages this intuition in the context of one-shot architecture search (Bender et al., 2018). In one-shot NAS, instead of evaluating several candidate architectures, single "base" neural network model is pre-trained; class of sub-netwon netwoss is identified (called the search space) and the performance of each sub-network is evaluated on a validation set; and the best-performing sub-network is finally selected and fine-tuned.
(a)
Figure 1: Overview of CoNAS. A one-shot neural network model f is pre-trained, and an appropriate sub-graph of f is chosen by applying sparse recovery technique. Iterative sparse recoveries allow to find the larger sub tub-graph from f.
Following Hazan et al. (2017); Stobbe & Krause (2012), we model the sub-network selection as a sparse recovery problem. Concretely, consider a function f that maps sub-architectures of performance (validation loss). We assume that f can be written as sparse, low-degree polynomial in the (discrete) Fourier basis If the sparsity assumption is satisfied, then we claim the function can be reconstructed using a very small number of sub-network evaluations, thus reducing overall compute time. key challenge lies in defining a suitable search space: we propose one that is considerably larger than the one used in DARTS or ENAS, allowing us to (putatively) search over more diverse set of candidate architectures.
measure
2 BACKGROUND
We briefly describe one-shot neural architecture search techniques (Bender et al., 2018; Li & Tal- walkar, 2019); a supplementary description is available in Appendix A. Following the treatment given in the recent survey paper (Elsken et al., 2018), one-shot NAS approaches have three main components: a search space, a search strategy, and a performance estimation strategy.
Search Space. The goal of one-shot NAS is to find the best performing cell, a fundamental component from which more complex architectures are constructed via stacking. Following Liu et al. (2018b), a cell is a directed acyclic graph (DAG) where a node corresponds to the latent representation, and directed edge transforms predecessor nodes using given operation: common operations used in CNNs include x 3 and 5 x separable convolutions. x 3 max pooling, and 3 x 3 average pooling. Each cell has two input nodes and one output node, and intermediate nodes
2

---

Under review as a conference paper at ICLR 2020
only be connected by predecessor nodes including input nodes. Intermediate nodes are wired to two predecessor nodes CNNs and one predecessor node in RNNs.
Search Strategy and Performance Estimation Strategy. Having defined search space, one- shot NAS approaches employ four steps: (i) train a single "one-shot" base model that is capable of predicting the performance of sub-architectures' (ii) randomly sample sub-architectures of a trained one-shot model and measure performance over a hold-out validation set of samples; (iii) select the candidate (cell) with best validation performance; (iv) retrain deeper final architecture using the best cell. Using the one-shot model as the proxy measurements of the candidate architecture corresponds to the performance estimation strategy (first and second step).
Fourier analysis of Boolean functions. We follow the treatment given in O'Donnell (2014). A real-valued Boolean function is one that maps n-bit binary vectors (i.e., nodes of the hypercube) to real values: {-1, multilinear polynomials called the Fourier basis, defined as follows. (We denote the vectors with bold letters. Also, [r]] denotes the set (1,2...,1)) ..).)
R. Such functions can be represented in basis comprising real
Definition 2.1. For S S. [m], define the parity function Xs (-1,1}" - {-1,1} such that Xs (a) Ilis ag. Then, the Fourier basis the set of all 2" parity functions {xs}-
The key fact is that the basis of parity functions forms K K-bounded orthonormal system (BOS) with = 1, therefore satisfying two properties:
1, if T if T
(x) 1o
and
sup [xs(a)] < for all S C [n], (2.1) (-(,111)
Due to orthonormality, any Boolean function I has a unique Fourier representation, given by f(a) = Esgin x()) with Fourier coefficients f(S) (a (f where expectation is taken with respect the uniform distribution over the nodes of the hypercube.
modeling assumption that the Fourier spectrum of the function is concentrated on monomials of small degree (S d). This corresponds the case where f is decision tree (Hazan et al., 2017), and allows us to simplify the Fourier expansion by limiting its support. Let Pa C 2/nl be fixed collection of Fourier basis such that Pa= = [xs C 20d |S| S dJ. Then Pa C 2 induces function space consisting of all functions of order d or less, denoted by Hp, = {f Supplfi C Pa)) For example, P2 allows us to express the function I with at most E (T) = On?)) Fourier coefficients.
Lastly, if we have prior knowledge of some set of bits J, we use an operation called restriction.
Definition 2.2. Let f {-1,1}" + R. (J,J) be a partition of [n), and z {-1,1}7. The 1 11,
+ IR is the subfunction of f given by fixing restriction of f to J using denoted by fzye : 1, the coordinates in J the bit values
PROPOSED ALGORITHM: CONAS
Overview. Our proposed algorithm, Compressive sensing-based Neural Architecture Search (CoNAS), infuses ideas from learning a sparse graph (Boolean Fourier analysis) into one-shot NAS. CoNAS consists of two novel components: expanded search space, and a more effective search strategy.
Search Space. Our first ingredient is an expanded search space. Following the approach of DARTS (Liu et al., 2018b), we define a directed acyelic graph (DAG) where all predecessor nodes are connected to every intermediate node with all possible operations. We represent any sub- ub-ggraph of the DAG using a binary string a called the architecture encoder. Its length is the total number of edges in the DAG, and a (resp. -1) a indicates an active (resp. inactive) edge.
We note that the quality of sub-networt performance predictions is heavily dependent on the base model that is trained. Choosing the correct base model is itself separate challenge, which earlier papers such as Bender et al. (2018) have addressed in detail. We do not pursue that direction here since our focus is the sub-network selection prohlem, and assume that the hase model is well-trained.
3

---

Under review as a conference paper at ICLR 2020
Image
Cell.
Call. 1
Input
Input
Input
Input
Stem1
Cell
Choice
Choicel
Choice2
Concat
0114
Celli
Nodel
Choice3
Choice4
3x3
5x5
Identity
Max Pool
Avg Pool
Cell2
Choice5
3x3
5x5
Node2
Cell3
Softmax
Sum
Output
Figure 2: Diagram inspired by Bender et al. (2018). The example architecture encoder samples the sub-architecture for N nodes (two intermediate nodes) with five different operations. Each component in maps the edges one-to-one in all Choice blocks in cell. If a bit in corresponds to 1, the edge activates, while -1 turns off the edge. Since the CNN search space finds both normal cell and reduce cell, the length of is equivalent to + 3) 5 2 50.
Figure 2 gives an example of how the architecture encoder a samples the sub-architecture of the fully-connected model in of convolutional neural network. The goal of CoNAS is to find the "best" encoder ax, which "close enough" to the global optimum returning the best validation accuracy by constructing the final model with a encoded sub-graph.
Since each edge can be switched on and off independently, the proposed search space allows exploring cell with more diverse connectivity patterns than DARTS Liu al. (2018b). Moreover, the number of possible configurations exceeds similar previously proposed search spaces with constrained wiring rules Li Talwalkar (2019); Pham al. (2018); Real al. (2019); Zoph al. (2018).
Search Strategy. We propose compressive measuring strategy to approximate the ohe-shot model with a Fourier-sparse Boolean function. Let f {) - R map the sub-graph of the one-shot pre-trained model encoded by a to its validation performance. Similar Hazan et (2017), we collect small number of function evaluations of f. and reconstruct the Fourier-sparse function s f via sparse recovery algorithms with randomly sampled measurements. Then, we solve arg min, g(x) by exhaustive enumeration over all coordinates in its sub-cube 1} where (J,J) partitions [n] (Definition 2.2)². the solution of the arg min g(x) does not return enough edges to construct the cell (some intermediate nodes are disconnected), we simply connect the intermediate nodes to the previous cell output, Cell,-2, using the Identity operation (this does not increase neither the model size number of multiply-add operations). Larger cells can be found from multiple iterations by restricting the approximate function g and with fixing the values found the previous solution, and randomly sampling sub- sub-graphs in the remaining edges.
Full Algorithm. We now describe CoNAS in detail, with pseudocode provided in Appendix A.3. We first train a one-shot model with standard backpropagation but only updates the weight cor- responding the randomly sampled sub- sub-graph edges for each minibatch. Then, randomly sample sub-graphs by generating architecture encoder strings a E 1-1,1)" using a Bernoulli(p) distribution for each bit of independently (We set p 0.5).
In the second stage, we collect m measurements of randomly sampled sub-architecture performance denoted by y (f(a)), ((2)...... f(am)) Next, we construct the graph-sampling matrix A E {-1, 1, 1 | with entries
AI,* = Xs. (ai).
LE [m], k e [[Pa]] [m),1S] d,
(3.1)
where is the maximum degree of monomials in the Fourier expansion, and Sç the index set corresponding to th Fourier basis.
"This is similar to the idea of de de-biasing in the Hard- Soond-Treeholding (HT) algorithm (Foucart & Rauhut, 2017) where the support is first estimated, and then within the estimated support, the coefficients are calculated through least-squares estimation.
4

---

Under review as a conference paper at ICLR 2020
We solve the familiar Lasso problem (Tibshirani, 1996): aarggmin min l|y Axl12 + A||x||1
X" arg
(3.2)
xaaIPal
to (approximately) recover the global optimizer x', the vector contains the Fourier coefficients corresponding to Pa. We define an approximate function g = with Fourier coefficients with the top-s (absolutely) largest coefficients from x', and compute a arg min, 9(a), resulting all the possible points in the subcube defined by the support of (this computation is feasible if 8 is small). Multiple stages of sparse recovery (with successive restrictions previously obtained optimal o enable us to approximate additional monomial terms. Finally, we obtain a cell to construct the final architecture by activating the edges corresponding to all i [n] such that a² 1.
Theoretical support for CoNAS. The system of linear equations y = Ax with the matrix A [-1.1)mx0mr measurements y E Rm and Fourier coefficient vector x E ROO(") is an ill-posed problem when m & O(n²) for large n. However, if the graph-sampling matrix satisfies Restricted Isometry Property (RIP), the sparse coefficients, u can be recovered:
Definition 3.1. A matrix A Rmxx((") satisfies the restricted isometry property of order s with some constant if for every s-sparse vector u E [O("") (i.e., only entries are non-zero) the following holds:
(1 - 11112 = Aul S (1+ (1+0)|
We defer the history of improvements on the upper bounds of the number of rows from bounded orthonormal dictionaries (matrix A) for which A is guaranteed to satisfy the restricted isometry property with high probability in Appendix A.2. To the best of our knowledge, the best known result with mild dependency on 8 (i.e., 5 8-2) is due to Haviv & Regev (2017), which we can apply for our setup. is easy to check that the graph-samplingg matrix A our proposed CoNAS algorithm satisfies BOS for K = 1 (Eq 3.1).
Theorem 3.2. Let the graph-sampling matrix A 1-1,1) 11100()))( be constructed by laking m rows (random sampling points) uniformly and independently from the rows of square matrix M e (-1, xx0nn") Then the normalized matrix A with m Ollog" ((log(())0- log² (g)d log(n)) with probability least 2- O(dlog log(3)) 33) satisfies the restricted isometry property of order with constant 6; as a result, every s- s-sparse vector u E R0("")) can be recovered from the sample y: 's:
10(n*)]
= Au = Σ
uj AiA
j=1
by LASSO (equation 3.2).
Proof. First, we note that the graph-sampling matrix a BOS matrix with K 1; hence, directly invoking Theorem 4.5 of Haviv & Regev (2016) to our setting, we can see that matrix A satisfies
RIP. Now according to Theorem 1.1 of Candes (2008), letting 5 < v2 1, the l minimization or LASSO will recover exactly the sparse vector u. For instance, in our experiments, we have selected 1000 which is consistent with our parameters, d 2, 10, 140.
Here, it is worthwhile to mention two points: first, the above upper bound on the number of rows of the graph-sampling matrix A is the tightest bound (according to satisfy RIP. There exist series of results establishing the RIP for BOS matrices during the last 15 year. We have reviewed these results in the appendix A.2. Second, instead of LASSO, one can use any sparse recovery method (such as IHT (Blumensath & Davies, 2009)) in our algorithm. In essence, Theorem 3.2 provides a successful guarantee for recovering the optimal sub-network of a given size given a sufficient number of performance measurements.
knowledge) for the BOS matrices
4 EXPERIMENTS AND RESULTS
We experiment on two different NAS problems: (i) CNN search on CIFAR-10 CIFAR- 100, Fashion MNIST and SVHN, (ii) RNN search for Penn Treebank (PTB). We describe the training details
5

---

Under review as a conference paper at ICLR 2020
Table 1: Comparison with hand-designed networks and state-of-the-art NAS methods on CIEAR-10 (Lower test error is better). The results are grouped as follows: manually designed networks, published NAS algorithms, and our experimental results. The average test error of our experiment used five random seeds. Table entries with "_" indicates that either the field is not applicable or unknown. The methods listed in this table are trained with auxiliary towers and cutout augmentation. Running time cost is measured on NVIDIA TITAN X GPU. The reported time of CoNAS includes both training one-shot model and gathering measurements for the sparse recovery.
Test Error
Params (M)
Multi-Add
Search GPU days
Architecture
(%)
(M)
PyramidNet (Yamada et al., 2018) AutoAugment (Cubuk et al., 2019)
2.31
1.48
26
ProxylessNAS (Cai et al., 2019)
2.08
5.7
4
NASNet-A (Zoph al., 2018)
2.65
3.3
2000
AmoebaNet-B (Real et al., 2019)
2.55 0.05
2.8
3150
GHN (Zhang et al., 2018)
2.84:0000
5.7
0.84
SNAS (Xie et al., 2018)
2.85 0
2.8
1.5
ENAS (Pham et al., 2018)
2.89
4.6
0.45
DART' (Liu al., 2018h)
2.76 0.09
3.3
548
4
Random Search (Liu et al., 2018b)
3.29 + 0.15 0.15
3.1
4
ASHA (Li & Talwalkar, 2019)
2.85|3.03
2.2
RSWS (Li & Talwalkar, 2019)
2.71 + 0.08
3.7
634
2.7
DARTs (Li & Talwalkar, 2019)
2.62 0.12
3.3
DARTsf
2.59 0.13
3.4
576
4
CoNAS (t=1)
2.57 2.74 0.12
2.3
386
0.4
CoNAS (t=4)
2.55 2.62 + 0.06
4.8
825
0.5
CoNAS (t=1, (=60))*AutoAugnnn
1.87
6.1
1019
0.4
DARTS experimental results from Li & Talwalkar (2019).
Used DARTS search space with five operations for direct comparisons.
"C' stands for the number of initial channels. Trained 1000 epochs with Auto
for CIFAR- 10 and PTB in Sections 4.1 and 4.3 respectively. Our evaluation setup for training the final architecture (CIFAR-10 and PTB) the same as that reported DARTS and RSWS.
4.1 CIFAR-10
Architecture Search. We create a one-shot architecture similar to RSWS with a cell containing N = nodes with two nodes input and node as output; wiring rules between nodes different and as in Section We used five operations: x 3 and 5 x 5 separable convolutions, 3 x max pooling, 3 x average pooling, and Identity. On CIFAR-10, 10, equally divide the 50,000-sample training set to training and validation sets, following Li & Talwalkar (2019) and Liu et al. (2018b), We train one-shot model by sampling the random sub-graph under Bernoulli(055) sampling with eight layers and 16 initial channels for 100 training epochs. All other hyperparameters used in training the one-shot model are the same as in RSWS.
We run CoNAS in two different settings to find small and large size CNN cells. Specifically, we use 10, Fourier basis degree experiments with varying lasso coefficients in Appendix A.6). As a result, we found the normal cell and reduce cell with one sparse recovery stage as shown in Appendix A.4 (the larger CNN cells were found with multiple sparse recovery stages), Repeating four stages (t 4) of sparse recovery with restriction definition (2.2) returns an architecture encoder xx with numerous operation edges in the cells (Please Appendix A.9.1 for the found architecture). We support the effect of multiple stages sampling providing the empirical experiments on Appendix A.7. Now, we evaluate the model found by CoNAS as follows:
the sparsity parameters
and Lasso coefficient
(We include
Architecture Evaluation. We re-train the final architecture with the learned cell and with the same hyperparameter configurations in DARTS to make the direct comparisons. We use NVIDIA TITAN X, GTX 1080, and Tesla V100 for final architecture training process. CoNAS cells from four sparse

---

Under review as a conference paper at ICLR 2020
recovery stages (t=4) cannot the same minibatch size (i.e., 96) used in DARTs and RSWS, due to the hardware constraint; instead, we re-train the final model with minibatch size 56 with TITAN X. CoNAS architecture with one sparse recovery (t=1) outperforms DARTs and RSWS (stronger than vanilla random search) in test errors with smaller parameters, multiply-addition operations, and search time. In addition, CoNAS with four recovery stages (t=4) performs better than CoNAS (t=1) on both lower test егror average and deviation; however, it requires larger parameters and multiply-ade operations compared DARTs, RSWS, and CoNAS (t=l). We also train CoNAS (t=1) with increasing the number of channels from 36 to 60 and training epochs from 600 to 1,000 together with recent data augmentation technique called AutoAuggent (Cubuk al., 2019), which breaks through 2% test error barrier on CIFAR-10.
4.2 TRANSFER TO OTHER DATASETS
We test the cell found from CIFAR-IO to evaluate the transferability to different datasets: CIFAR-100, SVHN, and Mashion-MNIST in Table As we can see, CoNAS achieves the competitive results with the smallest architecture size compared to the other algorithms.
4.3 PENN TREEBANK
Architecture Search. Similar to the setup in DARTS and RSWS, CoNAS explores the cell with the following operations: Tanh, ReLU, Sigmoid, and Identity. We augment the RNN cell with variation of highway connections suggested by Pham et al Pham et al. (2018). Layers of depth in Recurrent Highway Network (Zilly et al., 2017) utilize a nonlinear transformation from its hidden state ht as follows:
h; (1 a) @ activation(h--1 w ( + 44-1 X c₁.
where "8" denotes the element wise multiplication. Since we use an expanded search space, we allow multiple operations; in such cases, we replace activation(hi-1 1,-11 with its sum-poote sum-pooled version, En activation (hi-1 W((h2.).
Pre-training the above RNN using weight-sharing can create unstable results since the sub- graphs could have some internal nodes with no connections, leading to exploding gradients. One way to mitigate this issue is to increase the p-parameter in the Bernoulli sampling to enforce connectivity: however, this can significantly slow down the computations. Hence, we add an additional heuristic of randomly activating an edge to connect the intermediate node if the node does not have any input edge according to its architecture encoder a.
After obtaining the one-shot model, randomly sample the measurements of the sub- aub-graph without the above hcuristic used in the training stage. Rumning CoNAS with two stages of sparse recovery with 10 and finds enough number of edges for the RNN cell. If the final resulting cells has intermediate nodes with a disconnected input, we added ReLU operations from the previous intermediate node. The visualization of the RNN cell found by CoNAS is shown in Appendix A.9.2.
Table 2: Image Classification Test Error of CoNAS on Multiple Datasets. We compare the performance of CoNAS on different datasets with existing NAS results. The experiment details for CoNAS described in Appendix A.5.
CIFARI00
SVHN
F-MNIST
Params (M)
Search (GPU days)
Architecture
(%)
(%)
(%)
SNAS* (Xie et al., 2018)
16.5
1.98
3.73
2.8
1.5
PNAS* (Liu et al., 2018a)
15.9
1.83
3.72
3.2
150
NASNet" (Zoph al., 2018)
15.8
1.96
3.71
3.3
1800
DARTs" (Liu et al., 2018b)
15.8
1.85
3.68
3.4
1
AmoebaNet-AA (Real et al., 2019)
15.9
1.93
3.8
3.2
3150
ASAP* (Noy al., 2019)
15.6
1.81
3.73
2.5
0.2
CoNAS (t=1)
15.9
1.44
4.11
2.3
0.4
This is the experimental result taken from Noy et al. (2019).

---

Under review as a conference paper at ICLR 2020
Table 3: Comparison of state-of-the-art NAS methods and hand-designed networks on PTB (Lower perplexity is better). The results are grouped in following orders: manually designed networks, published NAS algorithms, and our experimental results. The average test error of our experiment used five random seeds. Table entries with "." indicates either the field applicable or unknown.
Test Perplexity Valid
Params (M)
Search Cost GPU days
Architecture
Test
Variational RHN (Zilly al., 2017)
67.9
65.4
23
LSTM + DropConnect (Merity et al., 2018)
60.0
57.3
24
LSTM + Mos (Yang et al., 2018)
56.5
54.4
22
NAS (Zoph & Le, 2017)
64.0
25
le4
ENAst (Pham al., 2018)
56.3
24
0.5
Random search (Liu al., 2018b)
61.8
59.4
23
2
DARTs (Ist order)? (Liu al., 2018b)
60.2
57.6
23
0.5
DARTs (2nd order) (Liu et al., 2018b)
58.1
55.7
23
1
ASHA" (Li & Talwalkar, 2019)
58.6
56.4
23
RSWS (Li & Talwalkar, 2019)
57.8
55.5
23
0.25
DARTs (2nd order)*
60.7
58.0
23
RSWS
60.6
57.9
23
0.25
CoNAS
59.1
56.8
23
0.25
We used the RSWS code with adjusting the search time equivalent to CoNAS. Used NVIDIA GTX 1080Ti GPU for training/searching.
Used Tesla P100 GPU for training/searching.
Used NVIDIA Titan X GPU for wraining/searching
Architecture Evaluation. The results for recurrent architectures are presented in Table 3. We trained the final RNN model with the learned cell and the same hyperparameters in DARTs and RSWS, except with minibatch size equals 128 (due to hardware constraints). We also included the experimental results with RSWS methods allocating the equivalent search time with our methods to make a fair comparison with CoNAS. Since the published NAS literature in Table 3 uses different GPU hardware (e.g. DARTs and ENAS: NVIDIA GTX 1080Ti, RSWS: Tesla P100), a one-to-one comparison of the search cost value listed in Table 3 is not applicable. Our experiments show that CoNAS finds better performing architectures when compared with DART' and RSWS; however, note that these differ slightly from the published experimental results for DARTs and RSWS, which could not reproduce.
4.4 DISCUSSION
Noticeably, CoNAS achieves improved results on CIFAR-10 in both test enror and search cost when compared to the previous state-of-the-a algorithms: DARTs, RSWS, and ENAS. In addition, not only CoNAS finds the cell with smallest parameter size and multiply-add operations than the other NAS approaches, but also it obtains a better test enror with 2.57%. Many previous NAS papers have focused on the search strategy, while adopted the same search space (Zoph al., 2018) and (Liu et al., 20120188) 8b). Our experimental results highlight the importance of both seeking new performance strategies and the search space.
Finally, on PTB, our experiments show that CoNAS finds a better RNN architecture than RSWS, DARTs using an equivalent or less search However, the reported test perplexity of DARTs and RSWS outperforms both valid and test perplexity of CoNAS.
PRIOR ART
We conclude by briefly reviewing the NAS literature and highlighting connections with CoNAS.
Neural Architecture Search. Early NAS approaches used RL-based controllers (Zoph et al.. 2018). evolutionary algorithms (Real et al., 2019), or sequential model- based optimization (SMBO) (Liu al., 201 8a), and showed competitive performance with manually ddesined architectures such as
8

---

Under review as a conference paper at ICLR 2020
deep ResNets (He et al., 2016) and DenseNets (Huang al., 2017). However, these approaches required substantial computational resources, running into thousands of GPU-days. Subsequent NAS works have focused on boosting search speeds by proposing novel search strategies, such as differentiable search technique via gradient-based optimization (Cai et al., 2019; Liu et al., 201 8b; Noy et al., 2019; Luo al., 2018; Xie al., 2018) and random search via sampling sub-networks from a one-shot supernetwork (Bender et al., 2018; Li & Talwalkar, 2019). Other recent NAS approaches include RL approaches via weight-sharing et al., 201 8), network transformations (Cai et al., 2018; Elsken et al., 2019; Jaderberg et al., 2017; Jin al., 2018; Liu et al., 2017: Hu et al., 2019), and random exploration (Li al., 2018; Li & Talwalkar, 2019; Sciuto et al., 2019; Xie et al., 2019). To the best of our knowledge, no NAS method yet reported has explored compressive sensing techniques.
boost speeds compare to vanilla RL (Pham
Differentiable Neural Architecture Search (DARTs), Our CoNAS approach can be viewed as a refinement to DART's ((Liu et al., 2018h) which performs bilevel optimization by relaxing the (discrete) architecture search space to differentiable search space via softmax operations. The choice of alternative optimization on differentiable multi-objective formulation substantially speeds up the search by orders of magnitude while achieving competitive performance compared to previous works (Zoph & Le, 2017; Zoph et al., 2018; Real et al., 2019; Liu et al., 2018a).
One-Shot Neural Architecture Search. Bender et al. (2018) provide extensive experimental analysis on one-shot architecture search based on weight-sharing. Bender et al. (2018) statistically showed the correlation between the one-shot model (supergraph) and stand-alone model (subgraph) through the experiments. Li & Talwalkar (2019) proposes simplified training procedures without stabilizing techniques (e.g.. path dropout schedule on direct acyclic graph (DAG) and ghost batch normalization) from Bender et al. (201 8). As the final performance of the discovered architecture heavily relies on hyperparamettrr settings, Li & Talwalkar (2019) exactly accords hyperparameters and data augmentation techniques to DARTs for their experiments. This combination of random search via one-shot models with weight- provides the best competitive baseline results reported in the NAS literature. Our CoNAS approach improves upon these reported results.
Learning Sub-Networks. Stobbe & Krause (2012) propose learning sparse sub- uub-networks from small number of random cuts; they also leverage ideas from compressive sensing and provide theoretical upper bounds for successful recover. Our CoNAS approach is directly inspired from their seminal work. However, we emphasize essential differences: while Stobbe & Krause (2012) emphasize linear measurements, CoNAS takes a different perspective by focusing on measurements that map sub-networks to performance, which are fundamentally nonlinear. Moreover, our theoretical bounds use better Fourier-RIP bounds, and lead to improved results in terms of measurement complexity.
Hyperparameter optimization. Building upon the approach of Stobbe & Krause (2012), Hazan al. (2017) develop spectral approach called Harmonica for hyperparameter optimization (HPO) by encoding hyperparameters as binary strings. CoNAS also follows the same path, albeit for NAS. While NAS and HPO are sister meta-leaming problems, we emphasize that our focus is exclusively on NAS, while Hazan et al. (2017) exclusively focus on HPO.
Moreover, the techniques of Hazan al. (2017) cannot be directly applied the NAS problem. We need to define our search space, encode our search problem in terms of Boolean variables, and propose how to gather measurements. All these are new to our paper: in particular, CoNAS proposes gathering measurements within tractable sampling time described in Appendix A. while Harmonica naively gathers the approximated measurements by training the model for each randomly sampled hyperparameter choice. In Appendix 1, we show that describes the sampling times with the naive sampling method for 1,000 measurements takes approximately 174 GPU days, whereas CoNAS only take 0.02 GPU days to gather 1,000 measurements. Finally, Harmonica requires invocation of a baseline hyperparameter optimization method (such as random search, successive halving (Jamieson & Talwalkar, 2016), or Hyperband (Li et al., 2017)), which CoNAS does not require.
9

---

Under review as a conference paper at ICLR 2020
REFERENCES
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understanding and simplifying one-shot architecture search. Proc. Int. Conf. Machine Learning, 2018.
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 2009.
Jean Bourgain. An improved estimate in the restricted isometry problem. Geometric Aspects of Functional Analysis: Israel Seminar (GAFA), pp. 65, 2014.
Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang. Efficient architecture search by network transformation. Proc. Assoc. Adv. Art. Intell. (AAAI), 2018
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. Proc. Int. Conf. Learning Representations, 2019.
Emmanuel Candes, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 2006.
Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing. Comptes rendus mathematique, 346(9-10):589-59) 2008.
Emmanuel Candes and Terence Tao. Near-optimal signal recovery from random projections:
Universal encoding strategies? IEEE Trans. Inform. Theory, 2006.
Shengcao Cao. Xiaofang Wang, and Kris M Kitani. Learnable embedding space for efficient neural architecture compression. Proc. Int. Conf. Learning Representations, 2019.
Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of fourier matrices and list decodability of random linear codes. SIAM Journal on Computing, 2013.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation policies from data. IEEE Conf. Comp. Vision and Pattern Recog, 2019.
David L Donoho et al. Compressed sensing. IEEE Trans. Inform. Theory, 2006.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, arXiv preprint arXiv:1808.0533 2018.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient multiioojecttvve neural architecture search via lamarckian evolution. Proc. Int. Conf. Learning Representations, 2019.
Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sensing. Bull. Am. Math, 54:151-166 2017.
Ishay Haviv and Oded Regev. The list-decoding size of fourier-sparse boolean functions. ACM Transactions Computation Theory (TOCT), 8(3):10, 2016.
Ishay Haviv and Oded Regev. The restricted isometry property of subsampled fourier matrices. Geometric Aspects of Functional Analysis, pp. 163-179, 2017.
Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: a spectral approach. arXiv preprint arXiv: 1706.006664 2017.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. IEEE Conf. Comp. Vision and Pattern Recog, 2016.
Hanzhang Hu, John Langford, Rich Caruana, Saurajit Mukherjee, Eric Horvitz, and Debadcepta Dey. Efficient forward architecture search. Adv. Neural Inf. Proc. Sys. (NeurIPS). 2019.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks, IEEE Conf. Comp. Vision and Pattern Recog, 2017.
10

---

Under review as a conference paper at ICLR 2020
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojeiech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint arXiv:1711.09846. 2017.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial Intelligence and Statistics, pp. 240-248, 2016.
Haifeng Jin, Qingquan Song, and Xia Hu. Efficient neural architecture search with network morphism. arXiv preprint arXiv:8800 10282, 2018
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. Adv. Neural Inf. Proc. Sys. (NeurIPS), 2018.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search.
arXiv preprini arXiv: arXiv:/902.0777 1902.0768.0 2019.
Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. Massively parallel hyperparameter tuning. arXiv preprint arXiv: 1rX.v.1810.05934, 2018.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: novel bandit- approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):676566816 2017.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy, Progressive neural architecture search. Euro. Conf. Comp. Vision, 201 8a.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hi- erarchical representations for efficient architecture search. arXiv preprint arXiv:1711.00430 2017.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. Proc. Int. Conf. Machine Learning, 2018b.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Yan Liu. Neural architecture optimization. Adv. Neural Inf. Proc. Sys. (NeurIPS), 2018
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm language models. Proc. Int. Conf. Learning Representations, 2018.
Asaf Noy, Niv Nayman, Tal Ridnik, Nadav Zamir, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik-Manor. Asap: Architecture search, anneal and prune. arXiv preprint arXiv: 04123, 2019.
Ryan O' O'Donell. Analysis of boolean functions. Cambridge University Press, 2014.
Hicu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architccture search via parameter sharing. Proc. Int. Conf. Machine Learning, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe classifier architecture search. Proc. Assoc. Adv. Art. Intell. (AAAI), 2019.
Regularized evolution for image
Mark Rudelson and Roman Vershynin. On sparse reconstruction from fourier and gaussian mea- surements. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 2008
Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint 1xXiv:9022.03 2019.
Peter Stobbe and Andreas Krause. Learning fourier sparse set functions. Proc. Int Conf. Art. Intell. Stat. (AISTATS). 2012.
11

---

Under review as a conference paper at ICLR 2020
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), pp. 267-288, 1996.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. arXiv preprint arXiv:1904.0156% 2019.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search.
arXiv preprint arXiv: /812.0996, 2018
Yoshihiro Yamada, Masakazu Iwamura, Takuya Akiba, and Koichi Kise. Shakedrop regularization for deep residual learning. Proc. Int. Conf. Learning Representations Workshop, 2018.
Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W Cohen. Breaking the softmax bottleneck: A high-rank language model. Proc. Int. Conf. Learning Representations, 2018.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. Proc. Int. Conf. Learning Representations, 2018.
Julian Georg Zilly, Rupesh Kumar Srivastava, Jan Koutník, and Jürgen Schmidhuber. Recurrent highway networks. Proc. Int. Conf. Machine Learning, 2017.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. Proc. Int. Conf. Learning Representations, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. IEEE Conf. Comp. Vision and Pattern Recog, 2018.
12

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1
SUPPLEMENTARY BACKGROUND OF ONE-SHOT NEURAL ARCHITECTURE SEARCH
In this section, we explain the one-shot neural architecture search in more details regarding of three directions introduced by Elsken et al. (2018).
Search Space. First, we start with the search space, defining the principles of constructing neural architecture. As discussed before, simplifying the search space using human prior knowledge can help search algorithms to find an optimal candidate faster. However, it may limit the algorithm to find novel architecture beyond our knowledge due to human bias. One-shot neural architecture search methodology is not restrict to the specific search space (e.g. RSWS (Li & Talwalkar, 2019) uses the equivalent search space to DARTs (Liu et al., 2018b)).
Search Strategy Next, we have a search strategy which is considered as a methodology to find the best neural architecture. In the last two years, different methodologies for search space such as reinforcement learning, evolutionary algorithms, SMBO, Bayesian optimization, bilevel optimization, and randomness are introduced in NAS literature. For instance, one-shot architecture uses random search as a search strategy.
Performance Estimation Strategy. One-shot NAS aims reduce the computational cost for the searching with the surrogate model to estimate the sub-networks performance. The conventional performance estimating methods require the massive computational resources as each model need to be trained and evaluated separately. In particular, assume that our goal is to construct a CNN by using a proxy architecture through randomly selected cell samples by concatenating eight layers with 16 initial channels (This is the same proxy model setup in DART's.. Then, we measure the validation loss from 50 epochs trained model where each epoch takes five minutes of training. As result, the total sampling time to collect 1,000 randomly sampled of the architecture performance (which is the same number of measurements as our experiment using CoNAS with = 1) equals to 5 50 1000
24 = 174 days.
Instead, one-shot NAS trains the super- super-network with weight-sharing by randomly sample a sub- network and only update the weights corresponding to the sampled network for each minibatch. Bender et al. (2018) demonstrates the correlation between the performance of one-shot model and the stand-alone architectures. Moreover, Li & Talwalkar (2019) provides the experimental results that the random search with weight-sharing is competitive baseline even outperforming ENAS (Pham al., 2018).
A.2 PRIOR WORKS ON RECOVERY CONDITIONS ON COMPRESSIVE SENSING
There has been significant research during the last decade in proving upper bounds the number of rows of bounded orthonormal dictionaries (matrix A) for which A is guaranteed to satisfy the restricted isometry property with high probability. One of the first BOS results was established by Candes & Tao (2006), where the authors proved upper bound scales O(sa log" 6 n) for subsampled Fourier matrix. While this result is seminal, it is only optimal up to some polylog factors. In fact, the authors in chapter 12 of Foucart & Rauhut (2017) have shown necessary condition (lower bound) on the number of rows of BOS which scales as log 12)... In an attempt to achieve to this lower bound, the result in Candes & Tao (2006) was further improved by Rudelson Vershynin (2008) O(sd log(sd log r1) log n)). Motivated by this result, Cheraghehi et al. (2013) has even reduced the gap further by proving an upper bound on the number of rows as O(sd log s log n). The best known available upper bound on the number of rows appears be O(sd log s log" n); however with worse dependency on the constant 8, i.e., 8-4 (please see Bourgain (2014)). To the best of our knowledge, the best known result with mild dependency on (i.e., 8-2) is due to Haviy & Regev (2017), and is given by O(sd log" s log We have used this result for proving Theorem 3.2.
A.3 CONAS ALGORITHM
In this section, we provide the pseudocode of CoNAS explained in the Section 3 from the main paper.
13

---

Under review as a conference paper at ICLR 2020
Algorithm I CoNAS
1: Inputs: Number of one-shot measurements stage t, sparsity lasso parameter, X, Bernoulli
p
Stage 1 Training the One-Shot Model
2: procedure MODEL. TRAINING
3:
while not converged do
4: Randomly sample sub-architecture encoded binary vector according to Bernoulli(p)
5: Update weights Wa by descending V Ltrain(Ua
6: end while
7:
end procedure
Stage 2 - Search Strategy
8: procedure ONE-SHOT MODEL APPROXIMATION COMPRESSIVE SENSING
9:
for k E {l....,t) t} do Collect f...).... Solve
11:
arg min lly 2x +|////2
12:
Let 0i,,,,,_........ x2, .,,...,, x. be the absolutely largest coefficients of x". Construct
g(a) Σ x.((a)))
Compute minimizer z arg min (()) and let J the of indices of
14:
f= fJlz
end for
16:
Construct the cell by activating the edge where zi where E [m]]-
17:
end procedure
A.4
ARCHITECTURE FOUND FROM CoNAS FOR IMAGE CLASSIFICATION TASK
skip_ connect avg pool 3x3
sep_conv_5xx
skip_conner connect
(k-22
c_
(k-1)
sep_conv__3 3x3
max_pool_ _x3
(a) Normal Cell
(k-1]
skip connect
(k.2)
hop__cov_55vg 5x5 avg
coinect
rep_coav_5xc
slep
(k)
avg. pool, 3x3
sep_ 5xb
avg pool
(b) Reduce Cell
Figure 3: Convolution Cell found from CoNAS. The reduce cell found from CoNAS have a missing connection between Ck-1 and intermediate nodes which is a valid architecture in our search space.
A.5 TRAINING DETAILS ON OTHER DATASETS
This dataset extended version of CIFAR-10 with 100 classes containing 600 images each. Similar CIFAR-10, 10, CIFAR100 consists of 60,000 color images which splits into 50,000 training images and 10,000 test images. Following the existing works (Liu et al., 2018b), we train the architecture with 20 stacked cells equivalent CIFAR-10 setting. We train the architecture for
CIFAR-100
14

---

Under review as a conference paper at ICLR 2020
600 epochs with cosine annealing learning rate where the initial value is 0.025. We batch size 96, SGD optimizer with nestrov cestro--momentum of 0.9, and auxiliary tower with weights 0.4. For the regularization technique, include path dropout with probability 0.2, cutout regularizer with length 16, and Augmmnt (Cubuk et al., 2019) for CIFAR-100. Except AutoAugment, the training setup identical DARTs for CIFAR-10.
Street View House Numbers (SVHN) SVHN is digit recognition dataset of house numbers obtained from Google Street View images. SVHN consists 73,257 train digit images, 26,032 test digit images, and additional 531,131 images. We used both train and extra (total 604,388) images for the training the architecture. Due to the large dataset, we train the architecture for 160 epochs (equivalent to and other hyperparameter setup is equivalent to CIFAR-100.
Fashion-MNIST Fashion-MNIST concists of grayscale 60,000 train image set and 10,000 test image set with the size 28 28 associated with 10 classes of labels. Training hyperparameter setup of the final architecture is equivalent to CIFAR-10 10 without AutoAugment (Cubuk et al., 2019).
A.6 STABILITY ON LASSO PARAMETERS
We check our algorithm's is stability on lasso parameter by observing the solution given exact same measurements. Denote a== as the architecture encoded output from CoNAS given À = 1. We compare the hamming distance and the test error between a== and other values (A = 0.5, 2, 5, 10). The average support of the solution from one sparse recovery is 15 out of the 140 length. The average hamming distance between two randomly generated binary strings with supp(a") = 15 from 100, 000 samples 27.58 + 1.82. Our experiment shows stable performance under various lasso parameters with small hamming distances regards to various A. Also we measure the average test with 150 training epochs different values shown in Table 4. For the baseline comparison, we compare CoNAS solutions with the randomly chosen architecture with 15 operations.
Table 4: Lasso Parameter Stability Experiment.
Criteria
À 0.5
2.0
5.0
À
10.0
Random
Hamming Distance
8
12
29
Test Error (%)
3.74 + 0.07
3.74 + 0.07
3.51 = 0.06
3.62 = 0.04
4.43 = 0.08
Param (M)
2.3
2.3
2.6
2.6
2.7
Multiply-Add (M)
386
386
455
449
444
15

---

Under review as a conference paper at ICLR 2020
A.7 EFFECT OF MULTIPLE STAGES SAMPLING
We illustrate an experiment which shows that the CoNAS with multiple stages can successively discover important edges, and eventually find architecture with smaller loss/perplexity. Suppose sample 1,000) measurements and computed the mean and the standard deviation of the validation loss from CIFAR-10 (perplexity from PTB) for each stage, As we can see in Figure 4, the larger number of stages, the smaller loss/perplexity. While the multiple stage sampling finds more operation edges in the cell (equivalent finding larger sub-graph), it may increase the architecture size (in terms of parameters and multiply-addition operation) as shown in Table 1.
700
mean
Validation Loss of CNN
12
Valid Herplentty NNNN
10
800
400
8
300
1st
2nd
3rd
4th
1sl
2nd
3d
4h
Stage Iterations
Stage Iterations
(0) CIFAR-10
(b) Ponn Treebank
Figure 4: one- shot architecture validation loss/perplexity vs stage iterations (a) CIFAR- 10 and (b) PTB.
The line plot and shaded region correspond to the average and standard deviation measurements respectively.
A.8 EFFECT OF INCREASING OPERATION EDGES THE CELL.
We provide more experiments on training results of randomly wired cells which have a similar number of edges to the cell found by CoNAS (t=4). We randomly sampled the architecture code a with (inomiaa(140.) 1/4) for each digit being 1 that the expected number of total edges in normal cell and reduce cell 35. We randomly selected three architectures as shown Appendix A.9.5 and trained with the same settings to the section 4.1. Table shows that choosing larger number of randomly chosen edges not sufficient to improve the model's performance.
Table 5: Randomly Wired Model Performance on CIFAR-10. (Lower test error is better) Trained with auxiliary towers and cutout augmentation for 600 epochs (equivalent training setup to CIFAR-10 from DARTs
Method
Number of Edges
Size (M)
Test Error
Randomly Wired Model (1)
31
5.2
3.45%
Randomly Wired Model (2)
35
4.5
2.89%
Randomly Wired Model (3)
32
3.1
3.52%
16

---

Under review as a conference paper at ICLR 2020
A.9 ARCHITECTURE FOUND FROM OUR EXPERIMENT
A.9.1 COMPRESSIVE BENSING-BASED NEURAL ARCHITECTURE SEARCH (CONAS) FOR
CNN WITH FOUR STAGES OF SPARSE RECOVERY
[_1k-2]
skip comnect
skip CONTANT
MIp S-B 5c5
cep_conv_00 .55
scpy 36
seg 333
pax__ooo
4.14
skip
stp copy. DNG
slip connect
max axd
[-11
K0y pad
(a) Normal Cell
max pook 3x3
1.
skip puinect
sltp connect
Seppoom__SS
skip.comnct
mg pud
WV pool
pool 36d
2 06
max pool Jtl
copy 5i5
sop
skip_comncc
aggiaaL3 3x3
C1
(b) Reduce Cell
Figure 5: Convolution Cell found from CoNAS (t=4)
A.9.2
COMPRESSIVE SENSING-BASE NEURAL ARCHITECTURE SEARCH (CONAS) FOR RNN
relu
relu
relu
sigmoid
h
x_ (t)
ideetitt
identity
relu
Idaniity
[t-1]
identity
identity
identity
tanh
sigmaid
rehu
identity
Figure 6: Recurrent Cell found from CoNAS
17

---

Under review as a conference paper at ICLR 2020
A.9.3 DIFFERENTIABLE NEURAL ARCHITECTUrE SEARCH (DARTs) FOR CNN
skip_connee
skip_ connect
sep 3x3
c_ (k-2)
sep_conv _3x3
2
c_(k)
sep_conv _333
sep_ concoo.vv_c _33
sep conv _03
sep_conv conv_3xd _33
(a) Normal Cell
skip_connee connect
3
Skip_connect
(k)
(kk22)
avg pvg_pool 3x3
skip connect
skip_
2
max pool 3x3
pool_ _x33
dki__connect
[k-1)
(b) Reduce Cell
Figure 7: Convolutional Cell found from DARTs with the original setting in Liu al. (2018b).
18

---

Under review as a conference paper at ICLR 2020
A.9.4 CONAS SOLUTIONS WITH DIFFERENT LASSO PARAMETERS
skip connect
(k-2)
3
avg. pool 3x3
c_(k]
sep_conv _p__conv____ _onv_5x5
sep_conv conv 5x5
2
skip connect
pool 3x3
[k-1}
sep_ conv 3x3
(a) Normal Cell with =
avg pool_ol__5 3x3
avg avg_pool 3x3
skip_ conn_ct
sep_conv_ avg pool 3x3
(k-2)
sep_com hep_conv_5att
c_(k)
avg pool_3x3
(k(k1
skip_ akip_connect con_ 3x3
3
(b) Reduce Cell with À =
Figure 8: CoNAS cell with À corresponding Table 4.
skip_ connect
sep_comy canv_oovv___ __5
sep conv 5x5
max pool 3x3 avg_ 3x3
c_(k]
max hax__pol_333 3x3
c
sep sep_conv 3x3
c (k-2)
skip_ skip_connect
(a) Normal Cell with À 10
sep_conv conv 5x5
avg avg_pool pool 3x3
2
c_ (k-1)
C (k)
sep_conv __5
skip skin_connect
c_ (k-2)
skip_ cii_cconnect avg avg_pool 3x3
3
(b) Reduce Cell with À 10
Figure CoNAS cell with = corresponding to Table
19

---

Under review as a conference paper at ICLR 2020
A.9.5
RANDOMLY WIRED CNN ARCHITECTURES
avg avg. pool 3x3
sep_conn___ 3x3
1x
c_ (k-2)
sep_cont 5x5 sep
sea 5x5
3
330
skip
segt cony
(k-1)
sep_conv 3x3
skip
sep. ConY 5x5
C_(k)
sep ronv 3x3
séprcoav 353
(a) Normal Cell
sep_conv _33
avg pool 3x3
cep__cov___ 3x3
(k-2)
sep _anv_oovv____ 3x3
avg avg_pool__e p0ol_o3033
sep_conv conv 5x5
connect
ckip_connect 3
avg pool 3x3 avg. pool 3x3
ckk
avg pool
skip skip_connect
c (k11)
avg_ avg_pool_____ 3x3
skip_ connect
sep_conv_3xe
(b) Reduce Cell
Figure 10: Randomly wired cell corresponding to the first row result to Table 5.
20

---

Under review as a conference paper at ICLR 2020
ceny 3x3
skip connect
poo. 3x3
c_(122)
sep conv 5x5
max pool pool_xo 3x3
sep cony 3x.3
avg_ Lrg__pol_333 3x3
sep_conv 3x3
sep cep__oov__rs
sep_ _5x5
avg 3x3
C_(k
skip_ vonnect
skip skip_connect
skip comnect
pgg_ pooppoo.ss 3x3
c_(1-1]
sep cep_coyy____ 5x5
avg woo_ 3x3
skip connect
(a) Normal Cell
sep_come _e__conv__5
skip_connect
max max_pool _333
sep_conv_5x5
crip_connect
c_(k-2
avo_pool__t
skip connect
conv 3x3
avg pool 3x3
skip_connect
cony 3x3
sep_ cx5
avg _x3
max pool 3x3
(k)
akip_connect max pool 3x3
skip coip_connett
[k-1)
max maa_ppool___a
pool_3x3 .333
sep ccpp_coov... _o33_3x3
sep_conv 5x5
sep conv cop__5055_
skip_connect
(b) Reduce Cell
Figure 11: Randomly wired cell corresponding to the second row result to Table 5.
21

---

Under review as a conference paper at ICLR 2020
cen_covv_55 5x5
max pool_poop.c 3x3
[k(k]]]
max max__poo___ 3x3
sep_conv__s
avg_pool_3x3
skip compect
(k-)
sep_com convy __3x3
avg. wwg._oool_.. 3x3
max pool 3x3
skip connect
max_ max_pool__ae px3
avg_pool__ 3x3
C_(k)
(a) Normal Cell
avg wwg_pool_3xg 3x3
max_ pool 3x3
max ppoo__333 3x3
skip connect
skip_commee connect
conv 5x5
[k-1]
max 3:33
pool 3xc
avg poo__ 3x3
sep_ranv
sep cany 3x
c.(k)
(k-2)
sep_
sep_ cony, 3x.
skip_comnett connect
max pool_
sep_conv_5xx
max www._pool__e 3x]
max_ L_K_pool_33
(b) Reduce Cell
Figure 12: Randomly wired cell corresponding to the third row result to Table 5.
22

---

Under review as a conference paper at ICLR 2020
A.9.6 RANDOM SEARCH WITH WEIGHT-SHARING (RSWS) FOR RNN
sigmoid
3
tanh
relu
tanh
sigmoid
5
{t)
relu
x_(
x
tanh
2
h_(1-1>
tanh
Figure 13: Recurrent cell found from RSWS allocating equal amount search time to CoNAS
23


Reviews:
[{"review_id": "rygy26eptr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Contributions:\nThis paper tackles the problem of One-shot Neural architecture search by proposing a new method. \nThe method consists mainly of new search strategy of the optimal architecture that is inspired by the recovery of boolean functions from their sparse Fourier expansions. As such, this work is an application of recent progress in the field of compressive sensing to One-shot neural architecture search. Given the problem formalism, the authors have also provides guarantee for the optimality of their method, i.e the method can recover the optimal sub-network of any given  a sufficient number of performance measurements.\n\nClarity\nOverall, the paper is well motivated and the technical content is good. That said the structure could be enormously  improved to ease the reading and the overall understanding. For example: better caption for Figure 2 explaining what is shown; presenting the pseudo-code directly in the method overview and spending the rest of the section explaining the method; showing the related work before the experiments; etc.\n\nNovelty\nThe main novelty in my opinion is the application of compressive sensing methods to One-shot NAS. This approach is significantly different from other One-shot NAS method that I am aware of mainly regarding the search strategy employed to find the best architecture. \nHowever, this work seems like an incremental improvement over Hazan et al 2018. To this regard, the only novelty that was the framing of One-shot NAS as a recovery of boolean functions from their sparse Fourier expansions is not new either.  That is said, I am open to be proven wrong on this point!\n\nResults\nThe experiment section is not self-content, the readers is refered a couple of times to other papers to get details that are  critical to reproducibility and understanding. \nOverall, the search strategy of CoNAS seems  parameter efficient, fast and competitive. Also, small ablation studies showing the effect of the different parameters of CoNAS were very informative and well-appreciated.\nHowever,  the search space is different between CoNAS and the others methods for some experiments, making it difficult to decide if the search strategy of CoNAS is definitely competitive compared to other methods or not.\n\nPoints of improvement:\n1 - Structure of the paper\n2 - Clarify novelty compared to HARMONICA ( not the application domain please)\n3 - demonstrate that with the same search space your method is competitive.\n4 - Does m=1000 in your experiments satisfies theorem 3.2? What is the value of d in your experiments? Can you provide supporting experiments that answer those questions?\n\nPreliminary decision:\nFor now, I will say *weak reject* \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxy8jjAcH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new algorithm for one-shot neural architecture search (NAS) via compressive sensing. The authors propose a new search strategy, as well as a slightly different search space compared to DARTS [1], ProxylessNAS [2], etc. They use architecture samples from the one-shot model evaluated with the search parameters as a surrogate of the true objective in order to speed-up the search. Afterwards, these surrogate function evaluations are used to compute Fourier coefficients which are eventually used to optimize the vector of binary parameters encoding the architecture. \n\nOverall, I think the proposed algorithm is interesting and of practical usefulness. However, in terms of novelty, this work seems more to be an application of Harmonica [6] to the NAS problem (with small modifications in order to make it applicable). In page 10 you state some of the differences of your method with Harmonica. I agree that the number of function evaluations you use (coming from the one-shot model) is larger and computationally less expensive to obtain, however this does not guarantee that these are a good surrogate of the true objective that NAS aims to minimize, i.e. the validation/test accuracy of final (stand-alone) architectures . The empirical evaluations of their algorithm seem to outperform/be competitive compared to other NAS methods on all benchmarks used in the paper, however only DARTS is evaluated on their search space and the other results are taken from the corresponding papers. The paper is well-written and -structured with the caveat of being more than the recommended 8 pages.\n\nI will adjust my score depending on the authors responses concerning the following questions/issues:\n\n1. The correlation between the architectures evaluated using the one-shot weights and retrained from scratch, seems to be of crucial importance in your method, since you directly use the one-shot weights to collect the measurements, similarly to Random Search with weight sharing [3], ENAS [4] or Bender et al. [5]. What is the correlation of these measurements with the stand-alone architectures trained from scratch using the final evaluation settings? How did you tune the p in the Bernoulli distribution during the one-shot weight updates. According to Bender et al. [5] the ScheduledDropPath probability is an important hyperparameter affecting the aforementioned correlation.\n\n2. What is the main motivation for using 5 operations in the operation set and not 8 as in DARTS [1] for example? Does the main contribution in the competitive results come from the different search space or the search method?\n\n3. Is there any reference or proof for the correctness of Theorem 3.2?\n\n4. I think there are some parts that can be moved in the Supplementary, such as the pseudocode for the proposed algorithm or Figure 3, and some other parts that can be compressed, such as the Related Work section.\n\t\nReferences\n[1] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  DARTS: Differentiable architecture search.  In ICLR, 2019.\n[2] Han Cai, Ligeng Zhu, Song Han. ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware. In ICLR, 2019.\n[3] LIAM LI, AMEET TALWALKAR. Random Search and Reproducibility for Neural Architecture Search.\n[4] Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, Jeff Dean. Efficient Neural Architecture Search via Parameter Sharing. In ICML, 2018\n[5] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, Quoc Le. Understanding and Simplifying One-Shot Architecture Search. In ICML, 2018\n[6] Elad Hazan, Adam Klivans, Yang Yuan. Hyperparameter Optimization: A Spectral Approach\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJxQXdh-Fr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study Neural Architecture Search, which aims to automate design of neural network models. Their approach consists in using a two stage algorithm:\n-\tA first Neural Network $f$ is trained for predicting the performances of sub-architectures. Then binary sub-graphs coding the sub-architectures are uniformly sampled (Bernouilli(0.5)), and their performances y are evaluated thanks to the first Neural Network.\n-\tThe graph sampling matrix A, which is indexed by the m sampled architectures and the Fourier basis of size $O(n^d)$, is built. Then the optimization problem $x^*= \\arg\\min_x ||y – Ax||$ is solved using Lasso. The largest Fourier coefficients are chosen to build an estimate g of f. Finally, computing minimum of g, the architecture is generated. \n\nSince $m << n^d$, the optimization problem is ill-posed. Theorem 3.2 shows that if A satisfies the restricted isometry of order s, then the sparse coefficients x can be recovered.\nThe algorithm is evaluated and compared to the state-of-the-art on various image classification tasks and on RNN.\n\n\nMajor concern:\n\n1/ I did not find the proof of Theorem 3.2 in the main paper and in the appendix, so I do not buy it.\n\n2/ The authors claim that their algorithm performs better than the state-of-the-art, but according to tables 1,2,3, I did not find significant differences of performances in term of test errors.\n\n3/ The key idea of the algorithm is not well explained. A one-shot NAS f is pre-trained. f is assumed to be well-trained. Then it is approximated with a Fourier-sparse Boolean function. Why using an approximation if f is perfect? Do you expect to reduce the needed number of sampled architectures?\n\n\nMinor concerns:\n \nEquation 3.1 is not clear. $X_S (\\alpha_l)$ does not depend on k. So all rows seem to be the same.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed to use a compressive sensing approach for neural architecture search, similar to Harmonica for hyperparameter optimization. 

In the discussion, the reviewers noted that the empirical evaluation is not comparing apples to apples; the authors could not provide a fair evaluation. Code availability is not mentioned. The proof of theorem 3.2 was missing in the original submission and was only provided during the rebuttal. All reviewers gave rejecting scores, and I also recommend rejection. 
Decision: Reject