Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a DARTS variant named ZARTS, which replace the first-order and second-order approximations with zero-order approximations. Experiments on various datasets are conducted to show the superiority of ZARTS.
strengths_and_weaknesses: Strengths:
1. The inaccurate gradient estimation in first-order approximation could result in severe performance collapse and instability problems, this should be highlight in the community. This paper proposes a zero-order approximation method, which seems has better architecture optimization according to the paper's visualizations.
2. According to Table 5, ZARTS applies to various DARTS variants, and can bring consistent improvements to them.

Weaknesses:
1. The search cost of ZARTS is similar to DARTS (2nd). Many variants adopt first-order approximation instead of the second-order approximation for faster search, though it has inaccurate gradient estimations; while the proposed zero-order approximation has a similar cost as the second-order one, which may be a major limitation of this work.
2. Figure 1 is not sufficient enough to show the superiority of ZARTS in architecture optimization. I suggest the authors to conduct experiments on NAS benchmarks (e.g., NAS-Bench-201) to show the accuracy curves of architectures during the searching procedure.
questions: 1. Does ZARTS has the same memory cost as DARTS? Can ZARTS directly search on ImageNet?

2. Will the zero-order optimization still be accurate when searching on a huge search space?
limitations: Discussion of limitations was provided.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors reexamine the bi-level optimization of NAS and reveal that the differentiable assumption in DARTS can mislead the search process. To verify the analysis, they plot loss landscapes of DARTS and show that first-order approximation of network weight will distort the landscape and drift the optimal. To tackle such an issue, the authors propose ZARTS by utilizing zero-order optimization for architecture parameters. Specifically, they adopt three different zero-order optimizers and sufficient empirical evaluation demonstrates that zero-order optimization unanimously outperforms DARTS. Besides, the authors provide extensive convergence experiments to show the stability of ZARTS. In general, ZARTS provides a new insight for NAS task and achieves good performance on multiple search spaces and datasets.
strengths_and_weaknesses: Strengths:
1. The paper is well-written and the motivation is clear. The authors first reexamine the bi-level optimization of NAS, then analyze the fundamental limitations in DARTS, and lead to the introduction of ZARTS.
2. Illustration in Fig.1 is convincing, which provides enough evidence on the drawback of differentiable assumption of DARTS and the advantage of ZARTS against DARTS.
3. Apart from applying three zero-order optimization methods to NAS, the authors also theoretically show that ZARTS can degrade to DARTS under differentiable assumption.
4. The experimental results are impressive, showing that ZARTS outperforms DARTS and its variants on multiple search spaces and datasets. Besides, the authors conduct sufficient evaluation about the stability of ZARTS.

Weaknesses:
1. The authors base their zero-order search methods on three existing zero-order optimization algorithms. Of course it is fine with the current excellent analysis and nontrivial technical adaptation to the NAS problem, while it will be more impressive if the authors could propose their own zero-order algorithm tailored to NAS. I know proposing a new zero-order optimizer it self could be a prominent paper, so at least the authors could provide more discussion on this point.
2. The searching cost of ZARTS seems to be longer than other variants of DARTS (in Table 3) Can the authors provide more detailed discussion on the searching cost?

Overall, the motivation is clear and the evaluation is sufficient. The major concern is the search cost of ZARS, and I hope the authors could provide more analysis in the rebuttal.

questions: Please see the weakness. Besides, I notice that the variants of ZARTS, i.e., mergeZARTS and GZAS, requires fewer GPU memory, so my question is, can ZARTS directly search on ImageNet?
limitations: The limitations were discussed.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a new neural architecture search method, namely ZARTS, which solves the bi-level optimization through zero-order optimization. It provides interesting analysis on the differentiable assumption in DARTS and show that the assumption can distort the loss landscape and misleads the search target in Fig. 1. Then this work discards the differentiable assumption and turns to zero-order optimization techniques which to my knowledge have not been used in neural architecture search (NAS) literature. This work also shows the connection between ZARTS and DARTS and points out that ZARTS degrades to the first/second-order DARTS when the iteration number M=0 (for first-order DARTS) or M=1 (for second-order DARTS). The well-designed experiments on the search spaces of DARTS and RobustDARTS verify the effectiveness of ZARTS which are implemented in three variants with the tradeoff between efficiency and efficacy. The paper is technically clear and well written.
strengths_and_weaknesses: Strengths:

++ This paper provides new and interesting analysis on the limitations of differentiable assumption in DARTS, showing that it can distort the loss landscape resulting in the severe instability issue (in Fig. 1a). 

++ By showing the drawbacks of differentiable assumption, it is a good idea to adopt zero-order optimization methods to solve the bi-level optimization problem in NAS.

++ The theoretical analysis on the connection between ZARTS and DARTS are worth publishing, specifically: when the iteration number M is set as 0/1, ZARTS degrades to the first/second-order DARTS.

++ Experiments verify the efficacy of ZARTS, showing that zero-order optimization can effectively alleviate the instability issue of DARTS.

++ This paper provides three variants of ZARTS by combining with three variants of DARTS. Experiments indicate that the variants can speed up the search process and further improve the performance, showing the potential of zero-order optimization methods for NAS.

Weaknesses:

-- Zero-order optimization methods are known more inefficient than gradient descent method, so that ZARTS requires 1 GPU-day to search, which is more time-consuming than other DARTS-based methods.

questions: 1. This work introduces to apply three zero-order optimization methods to NAS. I wonder what properties for zero-order optimization methods are necessary to apply to NAS task? This question is also pertinent to the novelty of the paper, for better motivating the adoption of three specific zero-order optimization techniques presented in the paper.
2. Zero-order optimization methods are known more inefficient than gradient descent method. It would be better if the authors could provide more discussion on why ZARTS converges better than DARTS?

limitations: I think there is no particular limitation of this work.
review_title: null

Meta-review: metareview: This paper aims to solve the instability issues of differentiable architecture search (DARTS) using zero-order optimization. Three different optimization techniques are proposed and their efficacy is demonstrated successfully on several benchmark datasets and different variants of DARTS. Although there are some concerns regarding the computational complexity of zero-order optimization, the reviewers have found the contribution of this submission significant for acceptance at NeurIPS. Given this, we are happy to recommend acceptance.
confidence: Certain
Decision: Accept