MANAS: Multi-Agent Neural Architecture Search
Authors: Fabio Maria Carlucci
Pedro M Esperança
Marco Singh
Victor Gabillon
Antoine Yang
Hang Xu
Zewei Chen
Jun Wang
Venue:  (2020)
Keywords: Neural Architecture Search
NAS
AutoML
Computer Vision

Abstract: The Neural Architecture Search (NAS) problem is typically formulated as a graph search problem where the goal is to learn the optimal operations over edges in order to maximize a graph-level global objective. Due to the large architecture parameter space, efficiency is a key bottleneck preventing NAS from its practical use. In this paper, we address the issue by framing NAS as a multi-agent problem where agents control a subset of the network and coordinate to reach optimal architectures. We provide two distinct lightweight implementations, with reduced memory requirements ($1/8$th of state-of-the-art), and performances above those of much more computationally expensive methods.
Theoretically, we demonstrate vanishing regrets of the form $\mathcal{O}(\sqrt{T})$, with $T$ being the total number of rounds. 
Finally, aware that random search is an (often ignored) effective baseline we perform additional experiments on $3$ alternative datasets and $2$ network configurations, and achieve favorable results in comparison with this baseline and other competing methods.

Under review as a conference paper at ICLR 2020
MANAS: MULTI-AGENT NEURAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
The Neural Architecture Search (NAS) problem is typically formulated as a graph search problem where the goal is to learn the optimal operations over edges in order to maximize graph-level global objective. Due the large architecture parameter space, efficiency is a key bottleneck preventing NAS from its practical In this paper, address the issue by framing NAS as multi-agent problem where agents control a subset of the network and coordinate to reach optimal architectures. We provide two distinet lightweight implementations, with reduced memory requirements (1 (1/8th of statc-of-the-art, and performances above those of much more computationally expensive methods. Theoretically, we demonstrate vanishing regrets of the form O(VT), with being the total number of rounds. Fi- nally, aware that random search is an (often ignored) effective baseline we perform additional experiments on alternative datasets and network configurations, and achieve favorable results in comparison with this baseline and other methods.
INTRODUCTION
Determining an optimal architecture is key to accurate deep neural networks (DNNs) with good generalisation properties (Szegedy et al. 2017 Huang al. 2017 He al. 2016 Han al. 2017 Conneau et al. 2017 Merit et al. 2018). Neural architecture search (NAS), which has been formulated graph search problem, can potentially reduce the need for application-specific expert designers allowing for wide-adoption of sophisticated networks in various industries. Zoph and Le (2017) presented the first modern algorithm automating structure design, and showed that resulting architectures can indeed outperform human-des -usannde state-of-the convolutional networks (Ko 2019: Liu et al. 2 However, even in the current settings where flexibility is limited by expertly- designed search spaces, NAS problems are computationally very intensive with early methods requiring hundreds or thousands GPU-days to discover state-of-the-art architectures Zoph and Le
2017 Real et al. 2017 Liu et al. 2018ab b).
Researchers have used a wealth of techniques ranging from reinforcement learning, where a controller network is trained to sample promising architectures (Zoph and Le 2017 Zoph et al. 2018 Pham et al. 2018), to evolutionary algorithms that evolve a population of networks for optimal DNN design (Real al., 2018 Liu al., 2018b). Alas, these approaches are inefficient and can be extremely computationally and/or memory intensive as some require all tested architectures to be trained from scratch. Weight-sharing, introduced in ENAS (Pham al.) 2018). can alleviate this problem. Even so, these techniques cannot easily scale to large datasets, e.g. ImageNet. More recently, gradient-based frameworks enabled efficient solutions by introducing a continuous relaxation of the search space. For example, DARTS (Liu et al. 2019) uses this relaxation to optimise architecture parameters using gradient descent in a bi-level optimisation problem, while SNAS (Xie al. 2019) updates architecture parameters and network weights under one generic loss. Still, due to memory constraints the search has to be performed on cells, which are then stacked 20 times for the final architecture. This solution is coarse approximation to the original problem as show in Section 6 of this work and Doe 2019). In fact, we show that searching directly over 20 cells leads to a reduction in test error (0.24 p.p.; 8% relative to Liu et al. 2019). ProxylessNAS. (Cai et al. 2019) is one exception, as it can search for the final models directly; nonetheless they still require twice the amount of memory used by our proposed algorithm.

---

Under review as a conference paper at ICLR 2020
To enable the possibility of large-scale joint optimisation of deep architectures we contribute MANAS, the first multi-agent learning algorithm for neural architecture search. Our algorithm combines the memory and computational efficiency of multi-agen aultt--gent systems, which is achieved through action coordination with the theoretical rigour of online machine learning. allowing us to balance exploration versus exploitation optimally. Due to its distributed nature, MANAS enables large-scale optimisation of deeper networks while learning different operations per cell. Theoretically, we demonstrate that MANAS implicitly coordinates learners to recover vanishing regrets, guaranteeing convergence. Empirically, we show that our method achieves oftte-of-the-eee accuracy results among methods using the same evaluation protocol but with significant reductions in memory (1/8th of Liu et al., 2019) and search time (70% of
Liu et al. 2019).
The multi-agent (MA) framework inherently scalable and allows us to tackle an optimization problem that would be extremely challenging to solve efficiently otherwise: the search space of single cell is 844 and there no fast way of learning the joint distribution, as needed by a single controller. More cells to learn exacerbates the problem, and this is why MA is required, as for each agent the size of the search space is always constant.
In short, our contributions can be summarised as: (1) framing NAS as a multi-agent learning problem (MANAS) where each agent supervises a subset of the network; agents coordinate through credit assignment technique which infers the quality of each operation in the network, without suffering from the combinatorial explosion of potential solutions. (2) Proposing two lightweight implemen- tations of our framework that theoretically grounded. The algorithms are computationally and memory efficient, and achieve state-of-the-an results on Cifar-10 10 and ImageNet when compared with competing methods. Furthermore, MANAS allows search directly on large datasets (e.g. ImageNet). (3) Presenting 3 news datasets for NAS evaluation to minimise algorithmic overfitting; and offering a fair comparison with a random baseline.
2 RELATED WORK
MANAS derives its search space from DARTS (Liu al. 2019) and therefore most related to other gradient-based based NAS methods that use the same search space. SNAS (Xie et (019) appears similar at high level, but has important differences: 1) it uses GD to learn the architecture parameters. This requires differentiable objective (MANAS does not) and leads to 2) having to forward all operations (see their Eqs.5,6), thus negating any memory advantages (which MANAS has), and effectively requiring repeated cells and preventing search on ImageNet. ENAS (Pham et al. 2018) is also very diffcrent: its use of RL implies dependence on past states (the previous operations in the cell). It explores not only the stochastic reward function but also the relationship between states, which is where most of the complexity lies. Furthermore, RL has to balance exploration and exploitation by relying on sub-optimal heuristics, while MANAS, due to its theoretically optimal approach from online learning, is more sample efficient. Finally, ENAS uses a single LSTM (which adds complexity and problems such as exploding/vanishing gradients) to control the entire process. and is thus following a monolithic approach. Indeed, at a high level, our multi-agent framework can be seen as a way of decomposing the monolithic controller into a set of simpler, independent sub-policies. This provides a more scalable and memory efficient approach that leads to higher accuracy, as confirmed by our experiments.
3 PRELIMINARY: NEURAL ARCHITECTURE SEARCH
We consider the NAS problem as formalised DARTS (Liu et al. 2019). At higher level, the architecture is composed of computation cell that is a building block to be learned and stacked in the network. The cell is represented by a directed acyclic graph with nodes and N edges; edges connect all nodes i.j from i to j where < J. Each vertex ( is a latent representation for i E (I...., . V). Each directed edge (i.j) (with < j) is associated with an operation (i-5) that transforms (.)) Intermediate node values are computed based on all of its predecessors as (0)) Σizz (zx) For each edge, an architect needs to intelligently select one operation (f-.)) from a finite set of K operations, O = {ou())}< where operations represents some function to be applied to (1)) to compute ()), e.g., convolutions pooling layers. To each of ((-2) (-) is associated
2

---

Under review as a conference paper at ICLR 2020
(6.2 of operational weights wi that needs to be learned (e.g. the weights of convolution filter). (i.j) Additionally, a parameter 0k E R characterises the importance of operation & within the pool O for edge (i, j). The sets of all the operational weights {wh (w))))) } and architecture parameters {a (t,5)
are denoted by w and a, respectively. DARTS defined the operation of++)) (a:) as
K
(x))
Σ
(8.5) Ok
(x)
k==1
in which a encodes the network architecture. The optimal choice of architecture is defined by
a' min (ival) w²(a)) s.t. w² arg min ((miin) (a, w)
(2)
The final objective is to obtain sparse architecture 2 (2())), Vi,j where ((.J) [z] [2(+,)) ...... "K 2x]
(6,5) with 2k for l corresponding to the best operation and 0 otherwise. That is,
for each pair (1,3) single operation is selected.
ONLINE MULTI-AGENT LEARNING FOR AUTOML
NAS suffers from a combinatorial explosion in its search space. A recently proposed ap- proach to tackle this problem is to approxi- mate the discrete optimisation variables (i.e., edges in our case) with continuous counterparts and then use gradient-baat based optimisation meth- ods. DARTS (Liu et al. 2019) introduced this method for NAS, though it suffers from two im- portant drawbacks. First, the algorithm is mem- ory and computationally intensive (O(NK) K) with K being total number of operations be- tween pair of nodes and N the number of nodes) as they require loading all operation pa- rameters into GPU memory. As result, DARTS only optimises over a small subset of 8 cells, which are then stacked together form deep network of 20. Naturally, such an approxima- tion bound to be sub-optimal, Second, evalu- ating architecture amounts to prediction a validation set using the optimal set of network parameters. Learning these, unfortunately, is highly demanding since for an architecture 2,, one would like to compute c(val) (Z,, unt) where w arg min,, c((rain)) (w, Zz). DARTS, uses weight sharing that updates w, once per architecture, with the hope of tracking wi over learning rounds. Although this technique leads to significant speed up in computation, it is not clear how this approximation affects the validation loss function.
Agents choose successor operations
(2)
(a
aa
a
(at
Policy updates
Feedback
A
Lass
Input
Output
MANAS with single cell. Between each pair of nodes, an agent A, selects action (i)) according to 700 Feedback from the validation loss is used to update the policy.
Figure 1:
Next, we detail a novel methodology based on a combination of multi-agent and online learning to tackle the above two problems (Figure DT. Multi-agent learning scales our algorithm, reducing memory consumption by an order magnitude from ONN)) to ONN) and online learning enables rigorous understanding of the effect of tracking wi over rounds.
4.1
NAS AS A MULTI-AGENT PROBLEM
To address the computational complexity we use the weight sharing technique of DARTS. However, we try to handle in a more theoretically grounded way the effect of approximation c. ((val) (Z,, wi)
by c. (val) (Z,, wy). Indeed, such approximation uncontrollable weight component. To analyse the learning problem with no stochastic assumptions on the process generating (L1...., ......,.) Lr} we adopt adversarial online learning framework.
lead to arbitrary bad solutions due to the
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1 GENERAL FRAMEWORK: [steps with asterisks (*) are specified in section
1: Initialize: Ti is uniform random over all j E {l,... N). And random wi weights.
2: For 1 1,..., T
3: Agent A, samples of ~ (a;) for all i (1...., N), forming architecture Z.
4: Compute the training loss C((rain) (at) C. [( (Zr; wt)
5: Update w1+11 for all operation af in Z, from wi using back poe-ppoopgattin.
Compute the validation loss C/>aa) (at) c/ra)) (Z,, W
6:
7: Update TH+1 for all i E [l....N] } using Z1..... 2n and c ..... c.
8:
Recommend 21+1, after round T, where a ~ t (a for all E NJ.
NAS as Multi-Agent Combinatorial Online Learning. In Section 3 we defined NAS problem where one out of K operations needs to be recommended for each pair of nodes (i, in a DAG. In this section, we associate each pair of nodes with an agent in charge of exploring and quantifying the quality of these K operations, to ultimately recommend one, However, the only feedback for each agent is the loss that is associated with a global architecture Z, which depends on all agents' choices.
We introduce N decision makers, AI,..., Ay (see Figure I and Algorithm D. At training round each agent chooses an operation (e.g., convolution or pooling filter) according to its local action- distribution (or policy) af nÝ. for all j E {l...., .N} with a: E .......K; These operations have corresponding operational weights w, that are learned in parallel. Altogether, these choices a; at= a....., ag define a sparse graph/architecture Z, a for which validation loss C/-=)) (Z,, w.) is computed and used by the agents to update their policies. After T rounds, an architecture is recommended by sampling d'141 ~ "T++ for all j (1...., ,N]. These dynamics resemble bandit algorithms where the actions for an agent A, are viewed as separate arms. This framework leaves open the design of 1) the sampling strategy x² and 2) how I is updated from the observed loss.
Minimization of worst-case regret under any loss. The following two notions of regret motivate our proposed NAS method. Given a policy ı the cumulative regret RT, and the simple regret r after T rounds and under the worst possible environment v, are:
T
T
Rj sup E
min Σ L.(a.) t=1
Ed(a), 1=1
sup E Σ (((a+1)) - min Σ (a (3) t=1
1=1
where the expectation is taken over both the losses and policy distributions and a = (a ( denotes a joint action profile. The simple regret leads minimising the loss of the recommended architecture 4T+11 while minimising the cumulative regret adds the extra requirement of having to sample, any time I, architectures with close-to-optimal losses. We discuss in the appendix E how this requirement could improve in practice the tracking of w by w;. We let Ca(a;) be potentially adversarilly designed to account for the difference between wi and w, and make no assumption on its convergence. Our models and solutions in Section 5 are designed to be robust to arbitrary La (ax)).
1j=1
5 SOLUTION METHODS
This section elaborates our solution methods for NAS when considering adversarial losses. We propose two algorithms, MANAS and MANAS-LS, that implement two different credit assignment techniques specifying the update rule in line 7 Algorithm [ The first approximates the validation loss as linear combination of edge weights, while the second handles non-linear loss. We propose two associated sampling techniques that specify line of Algorithm [ one minimising the simple regret ri, and one targeting the cumulative regret RT,
Agent coordination, combinatorial explosion and approximate credit assignment. Our set-up introduces multiple agents in need of coordination. Centralised critics use explicit coordination and learn the value of coordinated actions across all agents (Rashid et al. 2018), but the complexity of the problem grows exponentially with the number of possible architectures 2, which equals K We argue instead for an implicit approach where coordination is achieved through a joint loss function depending the actions of all agents. This approach is scalable each agent searches its local
4

---

Under review as a conference paper at ICLR 2020
action space- smace and finite- for optimal action-selection rules. Both credit assignment methods below learn, for each operation & belonging agent A,, quantity Bi (similar to in Section B) that quantifies the contribution of the operation to the observed losses.
5.1 MANAS-LS
Linear Decomposition of the Loss. A simple credit assignment strategy is to approximate edge- importance (or <dge-weight) by vector (3 E RKN representing the importance of all K operations for each of the N agents. 3g is an arbitrary, potentially adversarially-chosen vector and varies with time account for the fact that the operational weights w, are learned online and to avoid any restrictive assumption on their convergence. The relation between the observed loss C! and the architecture selected at each sampling stage is modeled through linear combination of the architecture's 's edges (agents' actions) as
C. val) = 3.
(4)
where Z. E {0, 1l KN is a vectorised version the architecture Z, containing all action choices. After evaluating S architectures, at round we estimate ,3 by solving the following via least-squares:
Credit assignment: B, min Σ (c!val) B zT).
Though simple, the solution gives an efficient way for agents to update their corresponding action- selection rules which they implicitly coordinate. Indeed, in Appendix [C] we demonstrate that the worst-case regret Rí (3) can actually be decomposed into agent-specific form Ri (T'', v²) defined in the appendix: Rj = sup, ()) > supyi R4 (T (T², v²) = N. This decomposition allows us to significantly reduce the search space and apply upcoming sampling techniques for each agent A, in completely parallel fashion.
Zipf Sampling for ri.. A, samples an operation proportionally to the inverse of its estimated
rank (.) where (k)), is computed by sorting the operations agent A, w.r. B [k],, as
Sampling policy: T [k] = 1 11)()) [o) where logK 1 +/2 1/K.
Zipf explores efficiently as, up to log factors, for 1 S m < K, the m estimated best operations are picked uniformly ignoring the remaining K m operations: All operations are explored almost as in uniform exploration while the estimated best is picked almost all the time. The Zipf law is anytime, parameter free, minimises optimally the simple regret in multi-armed bandits when the losses are adversarially designed and adapts optimally to stationary losses (Abbasi- Yadkori et al. 2018).
5.2 MANAS
Coordinated Descent for Non-Linear Losses. As the linear approximation is likely to be crude, an alternative is to make no assumption on the loss function and have each agent directly associate the quality of their action with the loss g(val) (a:). This results in obtaining all the agents performing coordinated descent approach to the problem. Each agent updates for operation & its [k] as
Credit assignment:
[ = B + C.(al) 1 - [k)..
(6)
Softmax Sampling for Ri.-. Based on EXP3 Auer et al. 2002). samples are from a softmax distribution (with temperature 11) w.r.t. Bi and the aim is to always pull the best operation
Sampling policy: [ exp (1))
Σ exp (nB:il) for =,..... K.
Comments on credit assignment. Our MA formulation provides a gradient- free, credit assignment strategy. Gradient methods are susceptible bad initialisation and can get trapped in local
5

---

Under review as a conference paper at ICLR 2020
minima more easily than our approach, which, not only explores more widely the search space, but makes this search in an optimal way, given by the multi- aulti--rmed candit/multii-geen framework. Concretely, MANAS can easily escape from local minima the reward is scaled by the probability of selecting an action (Eq. 6). Thus, the algorithm has a higher chance of revising its estimate of the quality of solution based on new evidence. This is important as one-shot methods (such as MANAS and DARTS) change the network-and thus the dnvironment-thrrugghon differently, MANAS' optimal xxporation-exploittiii 'oodd' solutions towards 'very good' solutions that do not live in the former's ' proximity; in contrast, gradient methods will tend to stay in the vicinity of a 'good' discovered solution.
the search process. Put allows the algorithm move away from
5.3 THEORETICAL GUARANTEES
MANAS. This algorithms runs EXP3 (Auer et al. 2002) for each agent in parallel. If the re- gret of each agent is computed by considering the rest of the agent as fixed, then each agent has regret [VTK log K) which sums over agents to O ON (NVTK log K). The proof in given in
Appendix D.2
MANAS-LS. We prove for this new algorithm an exponentially decreasing simple regret rt. O (e-THH), where is a measure of the complexity for discriminating sub-optimal solutions as H N (minj Brb] Bj [K]). where kj = minigssk B71)) and Bibl =
Ets A(Ai)
[j] The proof in given in Appendix D.1
6 EXPERIMENTS RESULTS
This section, we (1) compare MANAS against existing NAS methods on the well established Cifar- 10 dataset. (2) evaluate MANAS on ImageNet. (3) compare MANAS, DARTS and random sampling on 3 new datasets. Descriptions of the datasets and details of the search are provided in the Appendix. We report the performance of two algorithms, MANAS and MANAS-LS, described in Section
Search Spaces: we use the same CNN search space as Liu et al. (2019). Since MANAS is memory efficient, can search for the final architecture without needing to stack a posteriori repeated cells, and so our cells are unique. For fair comparison, ImageNet. Experiments on Sport-8, Caltech- 101 and MIT-67 in Section 6.3 networks. Search Protocols: for datasets other than ImageNet, we use 500 epochs during the search phase for architectures with 20 cells, 400 epochs for 14 cells, and 50 epochs for 8 cells. All other hyperparameters are as in Liu al. 2019). For ImageNet, we use 14 cells and 100 epochs during search. In our experiments on the three new datasets we rerun the DARTS code to optimise an 8 cell architecture; for 14 cells we simply stacked the best cells for the appropriate number of times.
use 20 cells on Cifar-10 and 14 on
6.3 use both and 14 cell
Synthetic experiment. To illustrate the theoretical properties of MANAS we apply it to the Gaussian Squeeze Domain experiment, problem where agents must coordinate their actions in order to optimize Gaussian objective function (Colby et al. 2015). MANAS progresses steadily towards zero regret while the Random Search baseline struggles to move beyond the initial starting point. Details and results are provided in Appendix F
6.1 RESULTS ON CIFAR- 10
Evaluation. To evaluate our NAS algorithm, we follow DARTS's protocol: we run MANAS 4 times with different random seeds and pick the best architecture based on its validation performance. We then randomly reinitialize the weights and retrain for 600 epochs. During search we use half of the training set as validation. To fairly compare with more recent methods, we also re-train the best searched architecture using AutoAugment and Extended Training (Cubuk et al. 2018).
Results. Both MANAS implementations perform well on this dataset (Table I.. Our algorithm is designed to perform comparably to Liu et al. (2019) but with an order of magnitude less memory. However, MANAS actually achieves higher accuracy. The reason for this is that DARTS is forced to search for an 8 cell architecture and subsequently stack the same cells 20 times; MANAS, on the other hand, can directly search on the final number of cells leading to better results. We also report our results when using only 8 cells: even though the network is much smaller, it still performs

---

Under review as a conference paper at ICLR 2020
Table I: Comparison with state-of-the-art image classifiers on Cifar-10. The four blocks represent: human-designed, NAS, MANAS search with DARTS training protocol and best searched MANAS retrained with extended protocol (AutoAugment 1500 Epochs 50 Channels).
Architecture
Test Error
Params (M)
Search Cost
Search
(%)
(GPU days)
Method
DenseNet-BC (Huang et al. 2017)
3.46
25.6
manual
NASNet-A Zoohh et al. 2018)
2.65
3.3
1800
RL
AmoebaNet-B RRall ct al.
2018)
2.55
2.8
3150
evolution
PNAS (Liu et al. 20188)
3.41
3.2
225
SMBO
ENAS Pham et al. 20188
2.89
4.6
0.5
RL
SNAS (ie et al. 2019
2.85
2.8
1.5
gradient
DARTS, stt order (Liu et al.
2019)
3.00
3.3
1.51
gradient
DARTS, 2nd order (Liu et al.
2019
2.76
3.3
41
gradient
Random + cutout (Liu et 2019
3.29
3.2
MANAS (8 cells)
3.05
1.6
0.8t
MA
MANAS (20 cells)
2.63
3.4
2.8t
MA
MANAS-L3 (20 cells)
2.52
3.4
41
MA
MANAS (20 cells) Autonuggent
1.97
3.4
MA
MANAS LS (20 cells) + AutoAAgment
1.85
3.4
MA
Search cost for 4 runs and test error is for the best result (for fair comparison with other methods).
Table Comparison with state-of-the- image classifiers on ImageNet (mobile setting). The four row blocks represent: human-designed, NAS, MANAS search with DARTS training protocol and best searched MANAS retrained with extended protocol (AutoAugment 600 Epochs + 60 Channels).
Architecture
Test Error
Params
Search Cost (GPU days)
Search
(%)
(M)
Method
ShuffleNet 2x (v2) Zhang et al.
2018
26.3
5
manual
NASNet-A (Zoph et al. 2018)
26.0
5.3
1800
RL
AmoebatNet-C (Real et al.
2018
24.3
6.4
3150
evolution
PNAS (Liu et al.
2018a
25.8
5.1
225
SMBO
SNAS Xie el al.
2019)
27.3
4.3
1.5
gradient
DARTS Liu et 2019
26.7
4.7
4
gradient
Random sampling
27.75
2.5
MANAS (search on C10)
26.47
2.6
2.8
MA
MANAS (search on IN)
26.15
2.6
110
MA
MANAS (search on C10) + AutoAAument
26.81
2.6
MA
MANAS (search IN) AutoAugment
25.26
2.6
MA
competitively with Ist-order 20-cell DARTS. This is explored in more depth in Section 6.3
Cai et al.
(2019) is another method designed as an efficient alternative to DARTS: unfortunately the authors decided to a) use a different search space (PyramidNet backbone; Han et al. (017)) and b) offer no comparison to random sampling in the given search space. For these reasons we feel a numerical comparison to be unfair. Furthermore our algorithm uses half the GPU memory (they sample 2 paths at a time) and does not require the reward to be differentiable. Lastly, we observe similar gains when training the best MANAS/MANAS-E architectures with an extended protocol (AutoAuument + 1500 Epochs + 50 Channels, in addition to the DARTS protocol).
6.2 RESULTS ON IMAGENET
Evaluation. To evaluate the results on ImageNet we train the final architecture for 250 epochs. We report the result of the best architecture out of 4, chosen on the validation set for a fair comparison with competing methods. As search and augmentation are very expensive we use only MANAS and not MANAS-LS, the former is computationally cheaper and performs slightly better average.
7

---

Under review as a conference paper at ICLR 2020
cells
calls
67
96-
88
72-
65-
88-
72-
70-
08
62
Caltech-101
84
Cattech-101
MT-67
MANAS
NA 15
Random
DARTS
MARAS
NAVAS 1S
Ranidom
DARTS
Comparing MANAS, random sampling and DARTS (Liu et al. 2019) 8 and 14 cells. Average results of 8 runs. Note that DARTS was only optimised for 8 cells due to memory constraints.
Figure 2:
Results. We provide results for networks searched both on Cifar- 10 and directly on ImageNet, which made possible by the computational efficiency of MANAS (Table When compared to SNAS and DARTS currently the most efficient methods, using the same search space, available-MANAS -MANAS achieves state-of-the-art results both with architectures searched directly on ImageNet (0.85 p.p. improvement) and also with architectures transferred from Cifar-10 (0.55 p.p. improvement.. We observe similar gains when training the best MANAS architecture with an extended training protocol (AutoAugment 600 Epochs + 60 Channels, in addition to the DARTS protocol).
6.3 RESULTS ON NEW DATASETS: SPORT-8, CALTECH- 101, MIT-67
Evaluation. The idea behind NAS is that of finding the optimal architecture, given any sets of data and labels. Limiting the evaluation of current methods Cifar- 10 and ImageNet could potentially lead to algorithmic overfitting. Indeed, recent results suggest that the search space was engineered in way that makes it very hard find bad architecture (Li and Talwalkar 2019; [Sciuto et al. 2019). To mitigate this, we propose testing NAS algorithms on 3 datasets (composed of regular sized images) that were never before used this setting. but have been historically used in the CV field: Sport-8, Caltech-101 and MIT-67, described briefly in the Appendix. For these set of experiments we run the algorithm 8 times and report mean and std. We perform this both for 8 and cells; we do the same with DARTS (which, due to memory constraints can only search for 8 cells). For our random baseline we sample uniformly 8 architectures from the search space. Each proposed architecture is then trained from scratch for 600 epochs as in the previous section.
MANAS manages to outperform the random baseline and significantly outperform DARTS, especially on 14 cells. It can be clearly from our experiments, that the optimal cell architecture for 8 cells is nor the optimal one for 14 cells.
Results. For these experiments can be found in Figure 2
Discussion on Random Search. Clearly, in specific settings, random sampling performs very competitively. On one hand, since the search space is very large (between 8112 and 8280 architectures exist the DARTS experiments: [Lu et al. (2019), finding the global optimum is practically impossible. Why is it then that the randomly sampled architectures are able to deliver nearly state-of-the-art results? Previous experiments (Sciuto et al. 2019 Li and Talwalkar 2019) together with the results presented here seem to indicate that the available operations and meta- strutstructure have been carefully chosen and, as consequence, most architectures in this space generate meaningful results. This suggests that human effort has simply transitioned from finding good architecture to finding good search space problem that needs careful consideration future work.
CONCLUSIONS
We presented MANAS, a theoretically grounded multi-agent online learning framework for NAS. We then proposed two extremely lightweight implementations that, within the same search space, outperform state-of-the-arr while reducing memory consumption by an order of magnitude compared Liu et al. (2019). We provide vanishing regret proof's for our algorithms. Furthermore, MANAS on 3 new datasets, empirically showing its effectiveness in a variety of settings. Finally, confirm concerns raised in recent works (Sciuto et al., 2019; Li and Talwalkar 2019 Doe 2019)
evaluate
claiming that NAS algorithms often achieve minor gains over random architectures. We however demonstrate, that MANAS still produces competitive results with limited computational budgets.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Yasin A Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Conference on Learning Theory (COLT), 2018.
Peter Auer, Nicolo Fesa-Bianchi Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48- 2002.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends() in Machine Learning, 5(1):1-122, 2012.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In International Conference Learning Representations (ICLR), 2019.
Nicolo Cesa Desa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System
Sciences, (155:1444-14222 2012.
Mitchell K Colby, Sepideh Kharaghani, Chris HolmesParker, and Kagan Tumer. Counterfactual exploration for improving multiagent learning. In Autonomous Agents and Multiagent Systems (AAMAS 2015), pages 171-179. International Foundation for Autonomous Agents and Multiagent
Systems, 2015.
Alexis Conneau, Holger Schwenk, Loic Barrault, and Yann Lecun. Very deep convolutional networks for text classification. In European Chapter of the Association for Computational Linguistics: Volume I, Long Papers, pages 1107-1116, 2017.
Ekin D Cubuk, Barret Zoph. Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation policies from data. (Ki::180550950) 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition (CVPR), pages 248-255, 2009.
J Doe. NAS evaluation is frustratingly hard. To appear, 2019.
Li Fei-Fei, Rob Fergus, and Pictro Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. Computer Vision and Image Understanding, 106(1):59-70, 2007.
David A. Freedman. On tail probabilities for martingales. The Annals of Probability, pages 100-118, 1975.
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In Computer Vision and Pattern Recognition (CVPR), pages 5927-5935, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Computer Vision and Pattern Recognition (CVPR), pages 47088 2017.
ByungSoo Ko. Imagenet classification leaderboard. https::/kobiso.gitta 1o/
2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Li-Jia Li and Li Fei-Fei. What, where and who? classifying events by scene and object recognition. In International Conference on Computer Vision (ICCV) pages 1-8, 2007.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv: 1002. 07638, 2019.

---

Under review as a conference paper at ICLR 2020
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. European Conference Computer Vision (ECCV), pages 19-34, 2018a.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hierar- chical representations for efficient architecture search. In International Conference on Learning Representations (ICLR), 2018b.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference Learning Representations (ICLR), 2019.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations (ICLR), 2018.
Hicu Pham, Melody Guan, Barret Zoph, Quae Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning (ICML), pages 4092-4101, 2018.
Ariadna Quattoni and Antonio Torralba. Recognizing indoor scenes. In Computer Vision and Pattern Recognition (CVPR), pages 413-420, 2009.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), pages 4292- 4301, 2018
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In International Conference on Machine Learning (ICMI.), pages 2902-2911, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe Le. Regularized evolution for image classifier architecture search. arXiv: 17X2::1802.00 01548, 2018.
Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv:1902.081444 2019.
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander A Alemi Inception-v4, Inception- ResNet and the impact of residual connections on learning. In AAAI Conference on Artificial Intelligence, 2017.
Sirui Xie, Hehui Zheng, Chumxiao Liu, and Liang Lin. SNAS: Stochastic neural architecture search. In International Conference on Learning Representations (ICLR), 2019.
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. ShuffleNet: An extremely efficient convolutional neural network for mobile devices. In Conference Computer Vision and Pattern Recognition (CVPR), pages 6856-6856, 2018
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations (ICLR), 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Computer Vision and Pattern Recognition (CVPR), pages 8697-87 10, 2018.
10

---

Under review as a conference paper at ICLR 2020
A DATASETS
10 The CIFAR-10 10 dataset (Krizhevsky, 2009) is a dataset of 10 classes and consists of 50, 000 training images and 10, 000 test images of size 32x32 We use standard data pre-processing and augmentation techniques, i.c. subtracting the channel mean and dividing the channel standard deviation; centrally padding the training images 40x40 and randomly cropping them back to 32x32; and randomly flipping them horizontally.
ImageNet. The ImageNet dataset (Deng et al., 2009) is a dataset of 1000 classes and consists of 281, 167 training images and 50, 000 test images of different sizes. We use standard data pre-processing and augmentation techniques, i.e. subtracting the channel mean and dividing the channel standard deviation, cropping the training images to random size and aspect ratio, resizing them to 224x224, and randomly changing their brightness, contrast, and saturation, while resizing test images to x 256 and cropping them at the center.
Sport-8. This is an action recognition dataset containing 8 sport event categories and a total of 1579 images (Li and Fei-Feil 2007). The tiny size of this dataset stresses the generalization capabilities of any NAS method applied to it.
Caltech-101. This dataset contains 101 categories, each with 40 to 800 images of size roughly 300x200 (Fei-Fei et al. 2007).
MIT-67. This is dataset of 67 classes representing different indoor scenes and consists of 15, 620 images of different sizes (Quattoni and Torralbal 2009).
In experiments Sport-8, Caltech- 101 and MIT-67, split each dataset into training set containing 80% of the data and a test set containing 20% of the data. For each of them, we use the same data pre-processing techniques as for ImageNet.
B IMPLEMENTATION DETAILS
B. METHODS
MANAS. Our code is based modified variant of Liu al. (2019) To set the temperature and gamma, we used as starting estimates the values suggested by Bubeck et al. (2012): :
with = 0.95 (n(
(K number of actions, n number of architectures seen in the whole training).
= 1.05 K (m) We then tuned them to increase validation accuracy during the search.
MANAS-LS. For our Least- solution, we alternate between one epoch of training (in which all B are frozen and the w are updated) and one or more epochs in which we build the Z matrix from Section 4 (in which both 3 and are frozen). The exact number of iterations we perform this latter step is dependant on the size both the dataset and the searched architecture: our goal is simply to have number of rows greater than the number of columns for Z. We then solve B, ( ") LL, and repeat the whole procedure until the end of training. This method requires no additional meta- pattmearrsssss.
Number of agents. In both MANAS variants, the number of agents is defined by the search space and thus is not tuned. Specifically, for the image datasets, there exists agent for each pair of nodes, tasked with selecting the optimal operation. As there are 14 pairs in each cell, the total number of agents is 14 x C, with C' being the number of cells (8, 14 or 20, depending on the experiment).
B.2 COMPUTATIONAL RESOURCES
ImageNet experiments performed on multi-GPU machines loaded with 8x Nvidia Tesla V100 16GB GPUs (used in parallel). All other experiments were performed on single-GPU machines loaded with 1 x GeForce GTX 1080 8GB GPU.

---

Under review as a conference paper at ICLR 2020
C FACTORIZING THE REGRET
Factorizing the Regret: Let us firstly formulate the multi-agent combinatorial online learning in more formal way. Recall, at each round, agent A; samples an action from fixed discrete collection {a, (a).A.)) K 1 Therefore, after each agent makes a choice of its action at round t, the resulting network architecture 2, is described by joint action profile a. = [ (A1,,1
a (Av).1 and thus, we will use 2, and a. interchangeably. Due to the discrete nature of the joint action space, the validation loss vector at round is given by ((val)
-(1 (c.)al) (2)
(2(K)) and
Z(aal) Thee interconnection between joint policy т and an environment v works a sequential manner as follows: at round t, the architecture 2, ( _ ..... 1,-1, ) ) is sampled and validation loss C.(va)) c((a))(2))))) (2,) is observed As we mentioned previously, assuming linear contribution of each individual actions the validating loss, one goal is to find policy π that keeps the regret:
for the environment one can write y= (( (val)
(Z)-a)
T
T Σ
RT(T,,) 12 = E
Z Σ
min
B z
small with respect to all possible forms of environment v. We reason here with the cumulative regret the reasoning applies as well to the simple regret. Here, 3, E RR is a contribution vector of all actions and Z: is binary representation of architecture Z, and F C. [0, 1j is set of all feasible architectures In other words, the quality of the policy is defined with respect to worst-case regret:
R2 sup (T)
Notice, that linear decomposition of the validation loss allows to rewrite the total regret 7 as sum of agent-specific regret expressions R.
(A) (T(A)), v(4.)) for i = I,...,N:
T
N
N
T
RT( RT(T, E
3 ((A)).T (A.)
min
Σ
(ALT z(di)
1=1 Z
E
I. (0)
N
T
T
3
( (((1)
min
Σ 3 B(A.).TT z(di)
2 Z
(
11-1o..
N
R (Ai)
(Ai) v(ai)
1=1
where Be =
3 AAN.T T
and Z, = Z (AI.
z Z(AW).TT. z
[Z(A.)T (AA)). T
are decomposition of the corresponding vectors on agent-specific parts, (.), and joint environment v = II ulAi), and 1/ (0) is unit ball with respect || llo norm centered at 0 in [0, 1]K, Moreover, the worst-case regret ( also can be decomposed into agent-specific form:
joint policy (-))
RS = sup (T
sup (A:i) (zr( b(di). i i= i= N. p(A))
This decomposition allows us to significantly reduce the search space and apply the two following algorithms for each agent A, in completely parallel fashion.
D THEORETICAL GUARANTEES
D.I MANAS-LS
First, we need to be more specific on the way to obtain the estimates 3(AA)) [k]]
Please notice, the observed reward is actually random variable
We assume that architecture is feasible if and only if each agent chooses exactly one action.
12

---

Under review as a conference paper at ICLR 2020
In order to obtain theoretical guaranties considered the least-square estimates as in assa-Bianchi
and Lugosi (012) as
N II म (A)
B. = c((a)) p Z, where P E [zz"] with Z has law TT(+) =
Our analysis is under the assumption that each Br E RKN belongs to the linear space spanned by the space of sparse architecture 2. This is not a strong assumption as the only condition on a sparse architecture comes with the sole restriction that one operation for each agent is active.
Theorem 1.
Let us consider neural architecture search problem in multi-agent combinatorial online learning form with N agents such that each agent has actions. Then after I rounds, MANAS-LS achieves joint policy {TT, 1i2 with expected simple regret (Equation 3 bounded by O (e (e-T/H) in
any adversarial environment with complexity bounded by H = (minn WEE :E B (()) [i]
((A)) T [KT)), where kg- minge(l......)) B/ ((A0Li] [i].
Proof. In Equation 9 we use the same constructions of estimates Br as in ComBand. Using Corol- and Lugosi 2012) we then have that B, is an unbiased estimates of B,
lary 14 in
Given the adversary losses, the random variables 3r can be dependent of each other and /. E [7] as te depends on previous observations at previous rounds. Therefore, we use the Azuma inequality for martingale differences by Freedman (1975).
Without loss of generality we assume that the loss c((a are bounded such that c/ (0. 1] for all I. Therefore we can bound the simple regret of each agent by the probability of misidentifying of the best operation P(K + a.
We consider fixed adversary of complexity bounded by H. For simplicity, and without loss of generality, we order the operations from such that B (A)) agents.
[1] [2 .... S BBA [K] for all
We denote for k: > 1, A = B k
(A:) B
[x and A = Az-
We also have Aminn as the smallest nonzero eigenvalue of M where M is M = El where Z is random vector representing sparse architecture distributed according to the uniform distribution.
P(K + a = P 7K E (1, KJ:
(
P
3k E {1....,K K} BBA [k]] BLAi 2
or
B
[
[1]
TA
2
2
< P
(((A)
B [1] BBA0)111 [1]
TAi
Σ
K
P
B
B
TAp
2
k=2
(a)
K
(A+)2T
exp
2. (oogg(K)/ K)/ //mmn
km
(A,)2T
< K exp
2.llo(())
where (a) is using Azuma's inequality for martingales applied to the sum of the random variables with mean zero that are Br, - Br.t for which we have the following bounds on the range. The range of BR., is Jo, (Kog(K)))minn)) Indeed our sampling policy is uniform with probability 1/log( K) therefore one can bound Br,t as in
Bianchi and Lugosi 2012 Theorem 1) Therefore we have
| Br,ll < Nlog K)/A/// /omin-
We recover the result with union bound on all agents.
13

---

Under review as a conference paper at ICLR 2020
D.2 MANAS
We consider simplified notion of regret that is regret per agent where each agent is considering the rest of the agents as part of the adversarial environment. Let fix our new objective as minimise
T
sup E
Σ
C. (val)
(A::) aai) (a,
min (I.......K) K)
Σ c.
(val) (a, a
where a_ is fixed set of actions played by all agents to the exception of agent A, for the T rounds of the game and y contains all the losses
{ (val)) (a)) TEE.
We then can prove the following bound for that new notion of regret.
Theorem 2. Let consider neural architecture search problem in multi-agent combinatorial online learning form with N agents such that each agent has actions. Then after T rounds, MANAS achieves joint policy {T, YT with expected cumulative regret bounded by O (NvTK log K).
(T)
Proof. First we look at the problem for each given agent A, and we define and look at
T
(TT(Ai, a_)) sup E
Σ (val)
(a: (Ac. a...)
vall
(a, a
min (L K}
We want to relate that the game that agent i plays against an adversary when the actions of all the other agents are fixed to a to the vanilla EXP3 setting. To be more precise on why this is the EXP3 setting, first have that C/ra)) (at) is function of a, that can take KN arbitrary values. When
fix a_i. C/aa)) (at (Ai) a-i)) is a function of a, (Ai)) that can only take K arbitrary values.
(A.) a_.)) aa,)) and then the game boils down to the vanilla ad- One can redefine L. [.i.(vaa) (a, (a)))) c. (vall) (a
versarial multi-arm bandit where each time the learner plays a ((A1) E fl,...,KK K} and observes/incur the loss C. (vall (a))). Said differently this defines game where the new s' contains all the losses as V/= (L, (Lv)(va)) (a(A)) T).a ((Ai) (1...))
For all a-;
2 (EXP3, a.:) S 2/ TK log( ())
Then we have
(EXP3) & sup 2v TK log(
a =2/TK log(
Then we have
Σ (EXP3) 2N 2N (og(K)
E RELATION BETWEEN WEIGHT SHARING AND CUMULATIVE REGRET
Ideally we would like to obtain for any given architecture 2 the value Leat (2)). However obtaining w (Z) arg min Lirain (w, Z) for any given fixed Z would already require heavy computations. In our approach the we that we compute and update is actually common to all Z, as wr replaces w² w' (Z.) This is simplification that leads to learning a weight un that tend to minimise the loss Ez- Loat 22, w( 2)] instead of minimising Lrat (2,, w Zz). If is concentrated on fixed Z then these two previous expressions would be close. Moreover when 7e is concentrated on Z then w, will approximate accurately w* (Z) after few steps. Note that this gives an argument for using sampling algorithm that minimise the cumulative regret as they naturally tend to play almost all the time specific architecture. However there is potential pitfall of converging minimal solution as w, might not have learned well enough to compute accurately the loss of other and potentially better architectures.
local
14

---

Under review as a conference paper at ICLR 2020
F
GAUSSIAN SQUEEZE DOMAIN EXPERIMENT
Random Search MANAS
20
15
10
5
20000
40000
60000
100000
iteration
Figure 3: Regret for the Gaussian Squeeze Domain experiment with 100 agents, 10 actions, / 10.
Empirical MANAS
Theoretical upper bound
100
cumulaativ (x1005)
40
20
20000
40000
60000
80000
100000
Iteration
Figure 4: Theoretical bound for the MANAS cumulative regret (2N /TK log K; see Appendix D.2 and the observed counterpart for the Gaussian Squeeze Domain experiment with 100 agents, 10 actions, μ = 1, = 10.
15


Reviews:
[{"review_id": "ryxNjXer5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 work built on top of DARTS. In their setting, each edge on the DAG (same as the one proposed in DARTS) has one agent associated with it and every agent maintains weights to propose operations. The author introduced two ways to update these weights: 1) solving a least squares assuming the validation loss decomposes linearly on the operations (MANAS-LS); 2) only update the weights for the activated operations (MANAS). Due to the usage of bandit framework, theoretical guarantees on the regret can be derived. \n\nBecause the distributed nature of the agents, this work is memory efficient and it allows searching directly on large datasets. The empirical results showed competitive performance in less GPU days comparing to  DARTS and recent variants.\n\nThe paper is well written. Apart from the theoretical contributions, the empirical evaluations are well done: the author used 3 more datasets instead of the usual CIFAR-10 and IMAGENET. Also, the random search are brought into picture which I think every NAS paper should include.  \n\nIt's surprising to see MANAS-LS sometimes outperform MANAS. For me, MANAS is a more principle way. Do the authors have more explanations? Why the test error of MANAS-LS + AutoAugment is missing in Table 1?\n\nIt's nice that the authors apply bandit framework to derive theoretical guarantees, but how close are these guarantees to the practice (for example on the benchmarks used in the work)? Is there some study for that? As there are not so many NAS works with theories, I think it would be nice if the authors could also comment on that.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "rkgJ-2Pm5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposed MANAS, which is based on DARTS, by approximating the problem space by factorizing them into smaller spaces, which will be solved by multiple agents. The authors claimed that this can simplified the search space so that the joint search can be more efficient to enable us to search a larger space faster. While the overall idea seems simple but the coordinating among agents can be difficult, where the authors proposed credit assignment techniques to address the issue. The final algorithm is evaluated on CV datasets as well as 3 new datasets. \n\nOverall, I found the motivation and proposed solution by the authors convincing. However, in a search space where random searcher is competitive, it is important for us to have an in-depth understanding on the proposed techniques. Especially when the experimental results is not fully comparable (it is difficult to control #params to evaluate the Test Error, and Search Cost being a one-time cost), I think the magnitude of the improvement showed in the experimental results itself might not be enough to justify this new approach. \n\nI am curious about the how does the number of agents affects the experimental results. It seems that it is not mentioned in the experiment section (or I might missed it?). And do we need to search for the best number of agents, which will add to the search cost?\n\nI am also curious on if one can combine other search algorithms with the similar idea on dividing the search space, e.g., using random search on a subspace in a coordinate descend fashion. It will be great if the authors can provide more in-depth analysis on different component of the proposed algorithm so that we can fully understand the source of improvement.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SyeqLMkfqH", "reviewer": "AnonReviewer1", "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": "In this paper,  the authors pay attention on the bottleneck in the NAS of its large architecture space which cause low efficiency. They introduce the multi agent reinforcement learning method to take the neural architecture search as a multi agent reinforcement learning problem.\n\nMain contribution is :(1) Framing the MAS as a multi agent problem. (2)Purpose two lightweight implementation. (3) Presenting 3 new datasets for NAS evaluation to minimize algorithmic over-fitting.\n\nIt seems like that it is the first work to combine multi agent reinforcement learning with NAS, and you have make complete proof about the algorithm's efficiency both mathematically and empirically. But from the view of multi agent reinforcement learning, there are also some points which make me confused.\n\nThe main problem is coordination, and I understand it as the agents in your work aim to get a joint action and the training process of them are independent, but we all know that in multi agent problems, the changing of agent's policy will cause change of the environment, so it will bring the instability, so I want to know that how you deal with the instability or whether the instability influence a lot in your work? Another problem may be not a theoretically problem that I want to know that have you made the guarantee of the consistency of agents' policies when using parallel training (May be the framework in coding process guarantee it ?) or the consistency is unnecessary to talk because it doesn't influence the result?", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a NAS algorithm based on multi-agent optimization, treating each architecture choice as a bandit and using an adversarial bandit framework to address the non-stationarity of the system that results from the other bandits running in parallel.

Two reviewers ranked the paper as a weak accept and one ranked it as a weak reject. The rebuttal answered some questions, and based on this the reviewers kept their ratings. The discussion between reviewers and AC did not result in a consensus. The average score was below the acceptance threshold, but since it was close I read the paper in detail myself before deciding.

Here is my personal assessment:

"
Positives:
1. It is very nice to see some theory for NAS, as there isn't really any so far. The theory for MANAS itself does not appear to be very compelling, since it assumes that all but one bandit is fixed, i.e., that the problem is stationary, which it clearly isn't. But if I understand correctly, MANAS-LS does not have that problem. (It would be good if the authors could make these points more explicit in future versions.)

2. The absolute numbers for the experimental results on CIFAR-10 are strong.

3. I welcome the experiments on 3 additional datasets.

Negatives:
1. The paper crucially omits a comparison to random search with weight sharing (RandomNAS-WS) as introduced by Li & Talwalkar's paper "Random Search and Reproducibility for Neural Architecture Search" (https://arxiv.org/abs/1902.07638), on arXiv since February and published at UAI 2019. This method is basically MANAS without the update step, using a uniform random distribution at step 3 of the algorithm, and therefore would be the right baseline to see whether the bandits are actually learning anything. RandomNAS-WS has the same memory improvements over DARTS as MANAS, so this part is not new. Similarly, there is GDAS as another recent approach with the same low memory requirement: http://openaccess.thecvf.com/content_CVPR_2019/html/Dong_Searching_for_a_Robust_Neural_Architecture_in_Four_GPU_Hours_CVPR_2019_paper.html
This is my most important criticism.

2. I think there may be a typo somewhere concerning the runtimes of MANAS. It would be extremely surprising if MANAS truly takes 2.5 times longer when run with 20 cells and 500 epochs than when run with 8 cells and 50 epochs. It would make sense if MANAS gets 2.5 slower when just going from 8 to 20 cells, but when going from 50 to 500 epochs the cost should go up by another factor of 10. And the text states specifically that "for datasets other than ImageNet, we use 500 epochs during the search phase for architectures with 20 cells, 400 epochs for 14 cells, and 50 epochs for 8 cells". Therefore, I think either that text is wrong or MANAS got 10x more budget than DARTS.

3. Figure 2 shows that on Sport-8, MANAS actually does *significantly worse* when searching on 14 cells than on 8 cells (note the different scale of the y axis). It's also slightly better with 8 cells on MIT-67. I recommend that the authors discuss this in the text and offer some explanation, rather than have the text claim that 14 cells are better and the figure contradict this. Only for MANAS-LS, the 14-cell version actually works better.

4. The authors are unclear about whether they compare to random search or random sampling. These are two different approaches. Random sampling (as proposed by Sciuto et al, 2019) takes a single random architecture from the search space and compares to that. Standard random search iteratively samples N random architectures and evaluates them (usually on some proxy metric), selecting and retraining the best one found that way. The number N is chosen for random search to use the same computational resources as the method being compared. The authors call their method random search but then appear to be describing random sampling.

Also, with several recent papers showcasing problems in NAS evaluation (many design decisions affect NAS performance), it would be a big plus to have code available to ensure reproducibility. Many ICLR papers are submitted with an anonymized code repository, and if possible, I would encourage the authors to do this for a future version.
"

The prior rating based on the reviewers was slightly below the acceptance threshold, and my personal judgement did not push the paper above the acceptance threshold. I encourage the authors to improve the paper by addressing the reviewer's points and the points above and resubmit to a future venue. Overall, I believe this is very interesting work and am looking forward to a future version.
Decision: Reject