Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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. 

Because 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.

The 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.  

It'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?

It'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.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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. 

Overall, 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. 

I 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?

I 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.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.

Main 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.

It 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.

The 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?
review_title: Official Blind Review #1

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