Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The assumption original DARTS is lack of theoretical guarantees. This paper supports the theoretical explanation of operation selection in DARTS. It shows that the operation weights is not only associated to the magnitude but also a second-order information called Influential Magnitude. By using this influential magnitude, DARTS algorithms performed better than other baselines on NASBench201, NAS-Bench-1shot1, Cifar10 and ImageNet search space. 

strengths_and_weaknesses: + Paper is clear and easy to follow.
+ Give a concretely theoretically interpretation for operation selection in DARTS, which is one of the most popular search algorithm in NAS community. 
+ Search performance by using proposed operation selection method is improved on different search spaces compared to DARTS and its variants . 
+ The proposed method is able to get the stable results in multiple search runs. 
+ Code is available. 

- The practical implementation should be based on many assumptions and approximations. 
- The improvement of ImageNet and Cifar10 is marginal. 
- The words/characters in Figure3 is very unclear and hard to understand. 
- Not too much practical.
questions: 1. Why not compare DARTS-PT in NAS-Bench-1shot1 to make it consistent with other experiments? 
2. How many runs in table2 and table3?
3. Is the Test error Multi includes singe test in the first column of table3? If so, why the 2.50% for DARTS-IM not in the range of 2.70±0.18? If not, why not merge them? 

limitations: See weaknesses.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper improves the operation search method in DARTS by leveraging the proposed influential magnitude. Instead of selecting the architecture operation with operation magnitudes, the influential magnitude uses second-order Taylor terms similar to influence functions. The authors show that their proposed methods improve the final test accuracy on NAS-Bench-201, NAS-Bench-1shot1, and DARTS search spaces and select less number of skip connections, which is the fundamental problem in DARTS-based approaches.
strengths_and_weaknesses: Strengths
* The paper is well written, and the idea of using influence-based operation selection is well motivated.
* The relation to prior work is well discussed, and most derivations in the paper look correct (there is some confusion in some parts of the equation, which I ask in the question section).

Weaknesses
* It is challenging to understand the training scheme of both DARTS-IF and DARTS-IM by reading the paper. I believe that the training algorithm similar to Algorithm 1 in [1] would help understand how both methods are trained and how these two proposed methods differ.
* I find the empirical analysis of DARTS-IF and DARTS-IM to be relatively weak to make the proposed methods convincing. It would be helpful if there were a more extensive analysis compared to DARTS-PT. For example, comparing test losses on search space S1, S2, S3, and S4 on multiple datasets and showing how much improvements DARTS-IM can make compared to PT-DARTS would make the paper much more convincing. Also, quantitative experiments showing that DARTS-IM selecting fewer skip connections would be helpful (instead of qualitative experiments observing some final converged cells). I have additional questions about the experimental procedure below.
* In Section 5, instead of using the Neuman-series to compute the inverse Hessian-vector product, the authors proposed to use empirical Fisher and compute the term using the Sherman-Morrison formula. I believe that the manuscript lacks a proper explanation for this approximation.
* DARTS-IM requires more hyper-parameters to obtain the final architecture as it requires computing iHVP (compared to PT-DARTS). What are additional hyperparameters that need to be tuned compared to DARTS-PT, and how much additional time do you require to tune these parameters? The algorithm of the proposed methods (as described above) could also benefit the readers trying to understand these points. 
* While the authors answered yes to the checklist, I could not find a section that describes all training details of DARTS-IF and DARTS-IM.

[1] Wang, R., Cheng, M., Chen, X., Tang, X., & Hsieh, C. J. (2021). Rethinking architecture selection in differentiable NAS. arXiv preprint arXiv:2108.04392.

questions: 1. In Section 2, the authors introduce the influence function as the product between the Hessian inverse and the gradient of the loss with respect to its parameters. However, in equation 3, the influence on the test loss function is defined as the product between $s_{\text{stest}}$ (following the notation from the original influence function) and the product between the Hessian inverse and the second-order gradient of the loss with respect to the inputs and model parameters. The second part measures the influence when the data point is perturbed rather than up-weighting the data point, and hence there is a mismatch between equation 2 and equation 3. In summary, in equation 3, $H^{-1} \nabla_x \nabla_\theta \mathcal{L}(z, \theta^*)$ should be replaced with $H^{-1} \nabla_\theta \mathcal{L}(z, \theta^*)$.
2. In equation 6, it would be helpful to state that it is assuming that the gradient of the loss equals 0.
3. Is there a reason why NS performs poorly compared to SH? The core difference is that NS approximates the inverse Hessian, but SH approximates the Hessian with the empirical Fisher. The former is not guaranteed to be PSD while the latter is guaranteed to be PSD, and I wonder if the authors tried using higher damping in NS. The analysis in Appendix F only considers the change in a number of batches.
4. Is there a reason why DARTS-IF performs worse than DARTS-IM in Table 1? I do not understand the statement that “results that DARTS-IF outperforms DARTS-PT verified the effectiveness of the influence function explanation,” as DARTS-IF also uses the influence-based measure, which the iHVP with the gradient of the supernet. I understand that DARTS-IF also required computing the iHVP and was wondering if DARTS-IF is also using SM for iHVP approximation.
5. In Appendix B.3, the authors use finite-difference methods to compute the matrix-vector product, which is a very crude approximation. I believe that this should be described at least in the main text.
6. The results of PT-DARTS in Table 3 seem to be lower than the previously published baseline (which I believe is 2.48). How did the authors obtain results for DARTS-PT (and other baseline methods)?
7. In Section 6.4, the authors aim to show that DARTS-IM works even though the network has not fully converged (the gradient is non-zero). However, I cannot completely understand what Figure 4 is doing. For DARTS-IM, is it doing operation search after x epoch of the supernet training? Why does DARTS fail after 20 epochs of training? Is it due to the skip connection selection issue? Furthermore, I believe that using different colours for DARTS and SM and the comparison with PT-DARTS would be helpful.

I am happy to raise my score if the above issues and questions are addressed.
limitations: The limitations of the work are described in Section 6.5. I believe the work does not have a potential negative societal impact.
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 paper studies the architecture selection method for differentiable NAS.
It proposes an influential magnitude score based upon the influence function to how sensitive is the supernet loss w.r.t. changes in the continuous relaxed architecture parameter, which can be used to determine the operation strength for discretizing final architecture from DARTS Supernet.
The advantage of the proposed is two folds: 1). Theoretically grounded  2). Practically, require no fine-tuning step compared with the perturbation-based selection method proposed in DARTS-PT.
Empirical results are reported mainly on NAS-Bench-1shot1, NAS-Bench-201, and DARTS Space (CIFAR-10), which show favorable results compared with relevant baselines (i.e. DARTS and DARTS-PT).
strengths_and_weaknesses: Strength:

1. Overall, the paper provides a solid attempt to improve architecture selection in NAS. The analysis in Section 3 and 4 on how to derive the influence of changing architecture parameter alpha on the validation loss through model weight is sound, and the corresponding theoretical results are satisfactory.
2. The proposed influence magnitude for measuring operation strength is theoretically justified and intuitive.
3. Empirical evaluations are overall throughout and solid, with an exception which I will explain in the weakness section.

Weakness:

1. The author displays the discovered architectures on S1-S2. It would be better to also report numerical evaluations on S1-S4 in tabular form. The reason is that S1-S4 proposed in RobustDARTS [1] is one of the first discovered scenarios where DARTS fails the most. Including numbers on these benchmarks would help to establish baselines for future works. Another reason for requesting numerical comparison is that architectures with minimal skip connections might not necessarily be optimal.
questions: 1. In Section 6.1, is the search on NAS-Bench-201 conducted on three datasets separately, or just CIFAR-10?
2. Figure 3 is skewed due to resizing and is hard to read, you may want to modify it.
3. Maybe you can try to use different colors for each curve in Figure 4 to make it easier to match with corresponding legends.
limitations: Yes, the paper explicitly addresses its limitations.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper revisits the operation selection part in differentiable architecture search and proposes to introduce the influence function to interpret the operation strength in the architecture selection. The key idea is to approximate the sensitivity of candidate operations in DARTS through influence functions. Although the DARTS has been the mainstream paradigm in NAS, no theoretical analysis has been conducted on its most important part, the operation selection. Different from the DARTS-PT which uses heuristic perturbation-based methods, the authors provide a theoretical and novel operation selection method with justifications and guarantees through influence functions. Apart from existing magnitude-based and perturbation-based operation selection methods, the authors devise a new influential magnitude to measure the operation importance for NAS, which measures the sensitivity of operation with second-order information. Results on most existing NAS search spaces verify the superiority of the proposed method.
strengths_and_weaknesses: **Strengths:**  
- The proposed method is novel and clear, and the paper is well-written and easy to catch up with. The authors focus on an important while under-investigated aspect in DARTS, operation selection, and for the first time introduce influence functions into the NAS community. The authors devise a general approach for architecture selection by measuring the sensitivity of candidate connections in architecture. This paper is the first attempt to adapt the influence functions theory to the network connection rather than the training data points, so as to make it possible to extend to other applications, e.g., network pruning and model quantization.  
- The author, for the first time, mathematically formulate the operation selection part in DARTS in terms of the sensitivity, which is completely different from existing magnitude-based (DARTS) and perturbation-based (DARTS-PT) methods. By leveraging Taylor approximation and implicit function theorem, the authors derive a new criterion under several mild assumptions. The theoretical analysis is sound and rigorous which is lacking in this community, and the authors also provide several approaches for practical implementation.   
- The authors conducted sufficient and solid experiments in a variety of NAS search spaces, including NAS-Bech-201, 1Shot1, DARTS, and S1-S4, along with a lot of insight ablation study and discussion. I especially appreciate the reproducible results along with the open-sourced code. The results on different search spaces and datasets verify the superiority of the proposed influential magnitude, which is inspiring and impressive with reproducibility. Although improvements on DARTS space are somehow marginal as we understand the results in this search space are usually reported with the best single search run in existing literature, the authors visualize the search architectures which avoid performance collapse that exists in the magnitude-based selection methods, making the results more convincing.  
- This work is relevant to the NeurIPS community, especially to the neural architecture search community. In the long run, I could see this paper raises awareness in the community to be conscious about the operation selection part in the supernet-based NAS, and also encourages the investigation to adapt the influence functions theory to other parts of the machine learning community, rather than only the training data points.

----------
**Weaknesses:**  
- The author does not provide an algorithm framework to show the general flow of the proposed method, making it hard to get the core idea at the first glance.  
- The DARTS-IF appears in Sec 6.1 without any descriptions before. The author is suggested to describe the algorithm flow of DARTS-IF and DARTS-IM.  
- The potential directions are not well discussed. For example, this paper adopts the influence functions to measure the operation importance in a supernet, while I think it is inspiring to design an influential magnitude for the structured network pruning in the future which needs more discussion.   
- Although this paper nicely presents the operation selection with influential magnitude, some typos also exist.
questions: - The proposed influential magnitude is derived when the supernet is trained to convergence. I am curious about its performance at the network initialization. For example, the SNIP [1] for network pruning at initialization also achieves competitive results. Whether the proposed method also shows a similar phenomenon?  
- Rather than applying influence functions to the supernet-based NAS, can it be applied to the model-based NAS method?  

[1] Snip: Single-shot network pruning based on connection sensitivity. ICLR, 2019
limitations: The authors discussed the possible failure and limitations of this paper in Sec 6.5. Although the authors cover the limitations of influence functions in deep neural networks, the computational complexity of the influential magnitude is not well discussed. In addition, the proposed influential magnitude is designed only for the supernet-based NAS, and the discussion of its application to the model-based NAS is lacking.
review_title: null

Meta-review: metareview: The paper proposes a novel architecture selection method for differentiable NAS based on influence function calculation. During the discussions reviewers still found several weaknesses of the paper, including 1) the novelty of the application of influence function in NAS, and it requires a series of approximation 2) The updated results from the authors show that the proposed method may not outperform existing approaches (DARTS-PT) in some cases. 

However, since architecture selection is an important but under-studied problem in NAS, and the proposed method is well-motivated, we still think this paper is a solid and novel attempt on improving NAS. We therefore decide to accept the paper. 
confidence: Certain
Decision: Accept