Interpreting Operation Selection in Differentiable Architecture Search: A Perspective from Influence-Directed Explanations
Authors: Miao Zhang
Wei Huang
Bin Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural architecture search
influence function
operation selection

Abstract: The Differentiable ARchiTecture Search (DARTS) has dominated the neural architecture search community due to its search efficiency and simplicity. DARTS leverages continuous relaxation to convert the intractable operation selection problem into a continuous magnitude optimization problem which can be easily handled with gradient-descent, while it poses an additional challenge in measuring the operation importance or selecting an architecture from the optimized magnitudes. The vanilla DARTS assumes the optimized magnitudes reflect the importance of operations, while more recent works find this naive assumption leads to poor generalization and is without any theoretical guarantees. In this work, we leverage influence functions, the functional derivatives of the loss function, to theoretically reveal the operation selection part in DARTS and estimate the candidate operation importance by approximating its influence on the supernet with Taylor expansions. We show the operation strength is not only related to the magnitude but also second-order information, leading to a fundamentally new criterion for operation selection in DARTS, named Influential Magnitude. Empirical studies across different tasks on several spaces show that vanilla DARTS and its variants can avoid most failures by leveraging the proposed theory-driven operation selection criterion.

Interpreting Operation Selection in Differentiable Architecture Search: A Perspective from Influence-iirected Explanations
Miao Zhang
Wei Huang", Bin Yang
1 Harbin Institute of Technology (Shenzhen) AAalborg University
RRIKEN AIP *East China Normal University
Changmiao@hit.oom edu. wei huang. vr@riken. jP; byangedase.eccu.cor wdw.uuuedu..c
Abstract
The Differentiable ARchiTecture Search (DARTS) has dominated the neural ar- chitecture search community due its search efficiency and simplicity. DARTS leverages continuous relaxation to convert the intractable operation selection prob- lem into a continuous magnitude optimization problem which can easily handled with gradient-descent, while it poses additional challenge in measuring the op- eration importance or selecting an architecture from the optimized magnitudes. The vanilla DARTS assumes the optimized magnitudes reflect the importance of operations, while more recent works find this naive assumption leads to poor generalization and is without any theoretical guarantees. In this work, leverage influence functions, the functional derivatives of the loss function, to theoretically reveal the operation selection part in DARTS and estimate the candidate operation importance by approximating its influence on the supernet with Taylor expansions. We show the operation strength is not only related the magnitude but also second- order information, leading to a fundamentally new criterion for operation selection in DARTS, named Influential Magnitude. Empirical studies across different tasks on several spaces show that vanilla DARTS and its variants can avoid most failures by leveraging the proposed theory-driven operation selection criterion.
Introduction
Neural Architecture Search (NAS) has been successfully applied to automating the process of neural network design for broad of deep learning fields [35 41 48 50). However, the early NAS methods are often heavily computatiinall-xxpusiee and require hundreds or even thousands GPU days (34]. To improve the efficiency for more practical applications, lot of recent works proposed based on one-shot (also known as weight-sharing paradigm [33] to improve the search efficiency significantly. Differentiable ARchiTecture Search (DARTS) (27). the most popular one-shot NAS method, has dominated this area since its appearance. DARTS leverages continuous relaxation to convert the intractable operation selection problem into a continuous magnitude optimization problem, which can be gracefully solved by gradient-descent based on the bi-level optimization [8]. A discrete architecture then derived based the optimized magnitudes through operation selection.
Although the continuous relaxation makes DARTS able to optimize the magnitudes with rigorous theoretical formulation and guarantees [51] in the supernet training part. poses additional challenge in selecting a discrete architecture from the optimized magnitudes that there is no existing work can give theoretical explanation. DARTS is based the weight-sharing paradigm (33, which
"Corresponding Author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Trained Supernet with weights and magnitude. (9'
Fine-tune train-
Directyy inberit weights from supernet for
Discratization
target d to get R
Influence function oppronimation
Ground fruth
Inheriing weights modal (97,0)
fine funed) model, of 30
Figure 1: Pictorial depiction of discretization part in DARTS. There is gap between the train- monn-thesscratee (or fine-tuned) weights Q based on after discretization and the trained supernet weights 0* This paper leverages influence functions to quantify the disparity between L(O", .) and L((0",á) á) and show how weights A changes with a. The discretization process can be the argmax adopted by DARTS (7], the perturbation- based DARTS-PT [40], and so on.
assumes that the derived discrete architecture with the trained supernet weights can predict its train- from-scratch performance. However, there is gap between the two groups of weights, as depicted in Figure ! The vanilla DARTS assumes the optimized magnitudes can reflect the importance of the candidate operations, while Wang et al. [40] empirically show that the operation magnitude does not necessarily indicate how important the operation is in a trained supernet. For example, DARTS prefers skip-contection [45] as its magnitude always dominates the remaining operations, while an architecture with intensive skip citi-coonections generally leads to poor performance. Accordingly, Wang al. [40] proposed heuristic perturbation-basee method, DARTS-PT, operation's 's influence on the supernet by alternatively removing each one to calculate the supernet performance drop. Despite DARTS-PT can partially relieve the failure of DARTS, we empirically found that DARTS-PT still prefers skip-connection than other operations. One potential reason is that skip-connection's 's magnitude is much higher than other candidate operations, and directly removing skip-comnection usually greatly deteriorates the supernet performance. In addition, DARTS-PP lacks theoretical explanations and guarantees. For example, the intuitive way to show the importance of candidate operation importance is the leave-one-on retraining [22.. while which should fine-tune the supernet get the performance drop after removing every operation rather than directly measuring the performance drop as DARTS-PT, since there also exists a gap between the two groups of weights, as visualized in Figure T Section 3 also give an analysis on why perturbation- based method fails.
measure each candidate
This paper focuses on filling the gap of theoretical explanations for the discrete operation selection part in DARTS. Instead of considering heuristic approach to measure the operation importance [27 40), this paper first rigorously shows how the architecture parameters discretization poses an influence on the supernet weights in DARTS, and estimates the supernet performance drop accordingly. Our method is motivated by influence function (22). which is originally designed to understand the effect of removing an individual training point, while we leverage Taylor's 's approximation supernet performance drop when removing candidate operation. In this way, we show the operation strength not only related to the magnitude but also second-ordes information, and we accordingly design new criterion for the operation selection in DARTS, called Influential Magnitude (IM). Then, to avoid calculating the inverse of the Hessian matrix with respect to the model weights, we further utilize the Neumann series [29] and Sherman-Morrison formula (37 to approximate the wverse-Hessian- Vector Products (IHVPs), making the proposed method applicable to DARTS. Finally, we verify the efffectiveness of our method on several NAS benchmark datasets and the common DARTS search space. To summarize, we make the following contributions:
interpret the
This paper deepens our understanding of the operation selection in DARTS. We reformulate the operation selection in DARTS by approximating its influence on the supernet with Taylor expansions, which can thus gracefully interpret how the validation performance changes when selecting different operations without any additional fine-tuning.

---

We theoretically reveal the operation strength is not only related to the magnitude but also the second-order information, and accordingly derive fundamentally new criterion to measure the operation sensitivity, which we call Influential Magnitude (IM), for architecture selection in DARTS. Further, to make the proposed criterion practical, we devise several methods to estimate the Diverse-esssian Vector Products (IHVPs) in calculating the second- order information.
Extensive experiments verify the effectiveness of the proposed criterion, which significantly improves the performance of vanilla DARTS and other baselines on the NAS benchmark datasets and the common DARTS search space. We show DARTS is still strong NAS baseline when considering a more reasonable and theory-driven operation strength metric.
Preliminaries: DARTS and Influence Function
Typically, NAS focuses finding cell structure that is represented directed acyclic graph (DAG) with nodes and E edges affiliated with operations, which is discrete and hard-to-optimize problem. To enable the gradient-descent for architecture search, DARTS 27 leverages softmax as the continuous relaxation function to transform the architecture search into a continuous magnitude optimization problem:
exp(a.)
L' exp(o.)))
where O contains all candidate operations and DARTS optimize the magnitude dg. which can be formulated as bi-level optimization problem [8]:
min L (0" (a),
(1)
s.t. 0* (a) = argming Leroin (f, a.)
where a the continuous architecture representation and 6 is the supernet weights. The nested formulation in DARTS is the same the gradient- based hyperparameter optimization with bi-level optimization, which has been validated in a broad applications [33 31 32). After the bi-level optimization, DARTS usually considers heuristic methods to derive the final architecture, where the most popular one is to select the operations with the highest magnitudes, á argmax((r). Despite its simplicity, more recent works architectures.
45
49 52
found that DARTS could hardly find satisfactory
Different from the majority of existing works that attribute the failure of DARTS its magnitude optimization part, which is under a rigorous theoretical formulation [31], we revisit DARTS from the perspective of the architecture selection and try reveal this part with theoretical explanations, where we aim to identify the operation that will contribute most to the supernet performance, through the lens of influence functions [22] mathematically model the architecture selection process instead of heuristics.
The influence function [8] is classic technique from robust statisties that reveals how model parameters change as we upweight or perturb a specific training sample, which has been applied in explaining lot of modern machine learning applications (2] 22 30 53). More specifically, given model with parameters 0* after trained on a full training set D, influence function aims to study the
change of parameters /r 0" when retraining the model parameters to 0" after deleting a specific training point z, that D = D z. Rather than retraining the model for every removed point, Koh and Liang (22) estimated the influence by upweighting the data point with some small e. With leveraging the Taylor expansions, the influence on the model parameters can be estimated as:
I(2, de
- -H 0*),
(2)
and its influence on the loss function of a test point Ftest accordingly calculated as:
dl( 0r) - 0*) Ho.'"
I(z,
(3)
de
The detailed derivation of the two influence functions can be found in 22 Based on 2 and
3
we can now approximate the validation performance drop when removing training point from training set without conducting the time-consuming retraining.

---

The original work of influence functions for modern machine learning 122. which is also called as first-order influence functions, only considers a very small change on 8 as it only changes one training point, so the first-order Taylor expansion is satisfied to calculate the influence. However, upweighting a group of data points may lead to large change on 0* [ which violates the small perturbation assumption of the first-order influence functions. To make the the influence function capture the model parameter change more precisely, Basu et al. [4] extended influence functions using second-order approximations under the assumption that the third-order derivatives of the loss function at optimum is small. For the quadratie loss, the third-order derivatives of the loss are zero or very small, and Basu et al. 4 empirically verified that the this assumption also approximately held for the classification problem with cross-entropy loss function.
Different from existing works that analyze the effects on model parameters of removing data points, this paper creatively adapts influence functions to estimate the importance of candidate operations on a trained supernet in differentiable architecture search. We also follow the assumption in 4 that neglect the third-order and higher derivatives of the loss, and analyze the operation selection part, which is an additional process after bi-level supernet training in DARTS, through the lens of influence function in the following sections.
3 Interpret Operation Selection through Influence Functions
This section aims to understand how the model parameters 0 (a.k.a. the supernet weights in DARTS) would change when we derive the discrete architecture from the optimized continuous operation magnitudes, a.k.a. architecture selection. In this paper, our analysis only focuses on this architecture selection part after the bi-level supernet training process is finished. To be more clearly, we first define the optimized operation magnitudes by DARTS and the validation loss is L(O*, aa for simplicity. Then, we define the architecture parameters change to â after discretization, and the corresponding ground-truth supernet weights and validation loss defined 0 and L(θ", at), respectively. Rather than deleting a single data point that only brings small changes on the model parameters (22), the change of architecture parameters can lead to a considerable change on 8, so we leverage the second-order approximation [4] to reveal the supernet weights change. With second-order Taylor expansion on 0r for L(0", a). we have:
with the optimized supernet weights 0*,
AC = _(0",,) L("0 .a) L("", .a) A0T aC(0",)) 1/2200 82 [(0",6) AA L("" .),
(4)
09
0800
where A0- = 0- - 0-, and L is the validation loss function in Eq. For example, when we only remove one candidate operation as DARTS-PT [40] to measure the operation importance, the influence of this discretization brings to 0 is AA, and the true validation loss change should be L(O", ,á) L( a:) stated in Eq.(4) rather than L( (() L("", ,a) used by DARTS-PT. As shown in Eq.44, we need to calculate A6 to get AC after we change the a to á, while we try to avoid the time- coneumnns retraining process through leveraging influence functions [22 to estimating 6".
Based on the implicit function theorem [2 [11, the validation loss change after discretizing a to can be approximated as the following theorem.
Theorem Suppose that DARTS obtains the optimized architecture parameter with supernet weights Or after supernet training, a changes to â when conducting architecture discretization, and the mram--foom-crateee scratch validation loss for â is L(O", â.. If the third and higher derivatives of the loss function C at optimum is zero or sufficiently small [4, and with oc .a)
O. we have
00
- 1/2 0c a)
T
000 a)
ac(60 à)
AC _(,",,) - L(0", aa) xe L( a:) - -(0" a)
(5)
00
0000
00
Theorem D states that we can estimate the train- scaa-s validation performance of â without any retraining. During the discretization process, we can apply the argmax on all edges by one-shot that = aagmax((a)) or only discretize one edge in each step, or remove one candidate operation from one edge as DARTS- -T [40] which can be formulated as the first part of Eq. (5). L(#", â) L( a). We prefer an iterative discretization process that only applies small change on a as DARTS-PT, since our theoretical analysis in the next corollary will show that the error bound of our approximation related to Aa = â a. Before our analysis, we give the following common assumptions, which are also considered in several recent bi-level optimization problems 15 51).

---

Assumption For any 0 and a) and -(),-) are Lipschitz continuous with Cy > 0 and C₁, O, respectively.
Assumption C(8,a) is twice differentiable with constant Cи and is X-strongly convex with around 8* (a).
Assumption V fll is bounded with constant C. >
Corollary Based on the Assumption
we could bound the error between the approximated
validation loss L( (:)
AC
+
L(
and the ground-truth L(0",00 (i) in DARTS with E
[((: a) L(0", â)
Ka
6
max
ac 203
where K = 11 +
20 ||Aa||] + o(1 Aall²).
CuCo
Compared with the argmax used in DARTS, we prefer the perturbation-
discretization method [40] as which only remove one operation at each step, since the above Corollary show that error bound of the approximated validation loss L("", &) increase with the magnitude of the change of a.
Influential Magnitude for Operation Selection in DARTS
Section provides an iterative solution measure the operation importance based Eq. 5 through individually ly removing each operation, while which needs to repeat n times (the number of all candidate operations for all edges in the supernet work). More important, since removing one operation poses a considerable change on a (o; - 0), the approximation error produced by (5) non-negligible which may affects the accuracy as stated by Corollary [ So. more practical solution to illustrate the importance of each operation is to estimate how the validation performance will change after posing infinitesimal change on a, a.k.a. operation sensitivity. In this section, we aim to investigate the operation importance through the lens of sensitivity (24). Different from Section 3 that removes one operation (a; + 0), this section only changes the a with an infinitesimal Ex, which means that we can now conduct first-order Taylor expansion on a for L(O", å). Further
with -odder Taylor expansion on 0 and assuming the local optimal 02 .x) = 0, we have: 86
AC L(O", a) L( .a) = 1/2AgT 8 L(((" a:) A0 AaT OC
(6)
0000
da
Similar to Eq.4 it is intractable to directly calculate A0, while we can leverage implicit function theorem approximate it. Theorem 2 presents how the validation performance changes after pose an infinitesimal change on a.
Suppose that DARTS obtains the optimized architecture parameter with supernet weights 8" after supernet training, and we pose an infinitesimal change on a. Based on implicit function theorem and under the assumption that the third and higher derivatives of the loss function at optimum is zero or sufficiently small (4). the change of validation loss can be estimated as:
Theorem 2
O2 C(0 a) H
0 C20 Aa.
AL
-(0",a) =C=(00-,0
C(0", aa) -1/2Ao
dad0
080a
8 c()" is the Hessian matrix. 8638
where H
From Theorem 2 we can observe the relationship between AL and Aa. To be more specifically, when we only consider an infinitesimal change on a, that Aa = 6 where is a column vector with all ones and & an infinitesimal scalar, the sensitivity of a can be defined as:
AC 1/2 1 O2 L(0 H
0 aa)",a)
(8)
Aa
dado
000a
Accordingly, we propose an Influential Magnitude to quantify the operation importance through the lens of sensitivity:
Definition 1 Influential Magnitude (IM):
Suppose DARTS obtains the optimized magnitude with supernet weights 0* after supernet training, the operation sensitivity can be defined as IM = (()".a)
c(0" -IT PC0 ..)
Body
883a
Definition shows we can replace the magnitude a with the operation sensitivity IM in the operation selection for DARTS, whose i-th value represents the importance of i-th candidate operation.
5

---

5 Practical Calculation on Operation Influence
For a large neural network, it is impractical calculate the second-order information, e-g., the Hessian matrix H. let alone the inverse of Hessian. Generally, the core challenge in calculation of As to the term
5 and 7 the
Vector Products (IHVPs), H - u 14 22 37.
0'010" .a) we follow DARTS [27 to utilize the finite difference approximation for the practical of 380a
calculation. The first technique for IHVPs is the conjugate gradient (CG) which converts the matrix inverse problem into optimization problem with 8-optimal solution. However, the standard CG can be slow with a large dataset as it needs to go through the whole training points in each step [П] The original paper [22 using influence function for modern machine learning problem leverages the Neumann series to approximate the inverse, that H = -k=o(1 - H)", with only consider the first t terms to approximate H -1 However, there is a strict condition in the Neumann series approximation that | I|| < 1, which can not be guaranteed in the practical implementation. Differently, we consider that H-1 = (( = 7 -k - -H)², where is a small enough value. The following lemma gives our Neumann series based implementation for IHVPs.
Lemma With small enough 7, and assuming is A-strongly convex at optimum, H H can be formulated as: H - 7 - Vo Vo + Vi + +... Vk, where H 8 2(00" .a) Vo- 77, and V1 = -11-- Vx- 7(1 - ~
0600
In the practical implementation, it is still hard to make sure L. is X-strongly convex and not easy to select an appropriate y. The work [5] empirically showed that the stochastic Neumann series estimation for IHVP is somehow erroneous, especially when the network is deep. As we know, the true Fisher information matrix converges to the Hessian matrix with the training loss approaches to zero. However, it is usually infeasible to calculate the exact Hessian Fisher matrix in large neural network. A practical approximation is called as empirical Fisher, which has been verified to be effective in variety of applications [ [9]. In addition, important advantage from empirical Fisher is that it allows to approximate the inverse of the Hessian based on the
-orriison formula. Although the empirical Fisher can not exactly match the true Fisher and there several active researches on its applicability 23 38), empirical Fisher is significantly more computationally- efficient, which obtains a good trade-off between the approximation and practical efficiency (37. Apart from Neumann series, we also consider Sherman-Morriso formula [14 37 (A + uv
A-1 A uy"""" A-1 1tv A calculate IHVPs. With empirical Fisher F 1 n Σラ= (Vol)) replacing
true Fisher F- VoJ(Vo IHVPs can be calculated as following.
Lemma When assume the empirical Fisher can approximate the Fisher matrix, and H is the Hes-
sian matrix 82 "2((0" .)) in the optimal point, the IHVPs 11v can be formulated as: 1116 F-vv=
2000 t.. T,
1, Te
FI v In N+VoL.Tr, =n-'v- 5 Fr. where L = E ()((6) that E is a cross-
entropy loss and R is the regularization term, F2 === = 4 ビ VoL,VoL, is the empirical Fisher, and Vol,
rj = VoCs which can be recurrently calculated through rj = 1j VoL, Ei= 1o N.V.C.
6 Experiments
In Section 3 and 4 we have theoretically interpreted the operation selection through individually measuring each operation's 's influence supernet, and accordingly devised an Influential Magnitude (I to replace the commonly-used magnitude for architecture selection. In this sec- tion, we conduct a series of experiments to analyze whether our proposed method leads better and more stable results in differentiable architecture search settings. We consider two NAS benchmark dataset search space, DAS-Bench-201 122 and
Table 1: Test accuracy (%) on WAS-Bench-201.
Method
CIFAR-10
CIFAR-100
ImageNet-16-122
Random
86.61=13.46
60.83:12.58
33.1319.66
DARTS DARTS-PT
54.30+0.00
15.61+0.00
16.32=0.00
89.63=#0.19
62.35++2.14
36.51
DARTS-IF 91.8410.84 1.29
42.50
DARTS-IM 93.61
71.31:10.40
44.98 1..36
Full comparison with SOTAs is in Appendix D We default use Cherman-Morrison for DARTS-IM in this experiment.
NAS-Bench- I Ishot 466, and the most popular DARTS search space 27 We verified the effec- tiveness of the proposed theory-driven method compared with two heuristic methods, argmax and

---

perturbation- basse selection, and show that the proposed Inftuential Magnitude can be applied to DARTS and its variants with greatly enhancing the performance.
6.1 Reproducible Comparison on Benchmark Datasets
To empirically verify the effectiveness of our method, we first run a series of experiments on the two and NAS-Bench- 1shot1. To make our results reproducible,
NAS benchmark datasets, NAS-Bench we only replace the selection part in DARTS with IM and keep the remaining part identical.
Table D summarizes the statistical comparison results on NAS-Bench-201 with different random seeds, where DARTS-IF, as described in Section 3 follows DARTS-PT PT that individually removes operation to measure the supernet performance drop, while DARTS-IM IM, as described in Section 4 calculates the operation sensitivity (influential magnitude) to replace the original magnitude. The Random baseline is to randomly select architectures without considering DARTS-PT leverage the argmax and perturbation-basee heuristic selection, respectively. As shown, DARTS-IF and DARTS- IM both significantly outperform the random baseline and the two heuristic baselines, where DARTS-IM achieves near-optimal results, a 94.29%, 72.67%, and 45.93% test aceuracy on CIFAR-10 10, CIFAR- 100, and ImageNet, respectively, in single run (DARTS-IM with Sherman-Morrison approximation and N = 20 under random seed 0).
0, and DARTS and
From the searched architectures in NAS-Bench-2011 we found that DARTS selects skip-connection for all edges as its magnitude usually outweighs other candidate opera- tions. The results of DARTS in NAS- Bench-201, which even poorer than the random baseline, also sug- gest that the magnitudes could hardly reflect the operation importance. Al- though DARTS-PT can partially re- lieve this issue by selecting one or two more convolutional operations, it still prefers ceimecoomettinns (se- lects 3 skip-connections for edges) where directly removing them still significantly affects the performance.
(a) Neumann series.
(b)
formula.
Ablation study N under two approximation methods, where x-axis N and y-axis represents test accuracy on CIFAR-10. The computational complexity increases with the square of N for Sherman-Morrison formula, and we set the maximal N = 40.
Figure 2:
On the contrary, our DARTS-IR IF and DARTS- IM can find valid architectures with more convolutional operations (with only one skip-connection). Results Table I verified the effectiveness of our influ- ence functions based selection methods, which outperform baselines by large margins. DARTS-IF similar to DARTS-PT while with an additional term to approximate the fine-tuned performance and the results that DARTS-IF outperforms DARTS-PT verified the effectiveness of the influence function explanation.
As discussed in Section 5 we can leverage dif- ferent methods to approximate the IHVPs in our IM. and Figure 2 also analyzes different approximation methods along with the number of batches N. As demonstrated, increasing N approximation
Table 2: Best test error (%) on MAS--Benc--1sse Ishotl.
Method
Space1
Space2
Space3
DARTS
6.17:00.9
6.3010.00
6.8010000
DARTS-PT
6.25110.05
6.28110.06
6.6910.21
can help the to more accurately catch the operation impor- tance and we empirically find that N = 30 is enough in the BeS--eenc dataset. How- ever, we also observe Neumann approximation is not stable which even obtains worse results with increasing number of batches, showing it is somehow erroneous in estimating IHVPs.
DARTS-IM
6.10.10.24
6.53.10.05 6.20.10.00
PC-DARTS PC-DARTS-PT 6.14.10.88
6.37=00.55
6.30
6.50+0.00
6.37.10.12
6.38.10.09
PC-DARTS-IM 5.90.10.24 6.20.10.22 6.10.10.08
I The HAS-Bench. Ishtl is another popular NAS benchmark dataset to analyze differentiable NAS methods, which built based on the NAS-Bench-101 (44) through dividing all architectures in NAS-Bench-100 101 into three different unified cell-based search spaces to enable differentiable NAS methods to be directly applied. NAS-Bench- shott contains 6240, 29160, and 363648 architectures in three spaces, respectively, where Space3 is much more complicated than the remaining two spaces.
7

---

In NAS-Bencer 1shot1, we tracked the searched architecture in every epoch under different operation selection paradigms. We considered two popular supernet training baselines, DARTS and PC-DARTS, and Table 2 summarised the best-searched architectures during the supernet training in different sub-search spaces in NAS-Bench- shott, As demonstrated, our IM can enhance the performance of DARTS and its variant PC-DARTS in different search spaces of 1 that our influence magnitude (IM) can find more competitive architectures than the default argmax, especially in the more complicated space. Compared with the perturbation strategy (PT), our IM is more effective to measure the operation sensitivity with obtaining better results in cases.
showing
6.2 Reproducible Comparison on DARTS Search Space
The DARTS search space is the most commonly-used space to evaluate the NAS methods, while most SOTAs only report the performance of their best searched architec- tures without analyzing the search statistics. To encourage reproducibility, we train the supernet with the same random seeds, and the trained supernet is utilized to derive the architecture under different operation selec- tion strategies. The comparison results are provided in T from which we can see that, compared with the argmax baseline, the architectures searched by our Influential
Table 3: Search results on DARTS space.
CIFAR-10 Single
Test Error (%)
ImageNet
Method
Multi
Best
DARTS PC-DARTS
2.76+00.09
3.02++0.45
26.9 / 8.7
2.57=0.00
2.92:+0.26
25.1 7.8
DARTS-PT DARTS-IM
2.61110.08
2.89110.31
26.1 8.2 25.0 7.6
2.50.10.10
2.70
We run the architecture search with multiple times, and average the different derived architecture's test error.
Magnitude obtain better performance on CIFAR-10 and ImageNet than DARTS and its variant PC-DARTS, and DARTS-PT on ImageNet, implying our method more stable to find valid and competitive architectures. We also plot the searched architecture examples with different selection methods in the DARTS space in the supplemental material. Although DARTS, PC-DARTS and DARTS-PT can find satisfying architecture after multiple runs, we found the argmax is hard to con- sistently obtain stable results. In addition, different from the perturbation- based operation selection which needs to fine-tune the supernet after the discretization of each edge that costs 0.4 additional GPU day for DARTS, our influential magnitude is calculated by one time which only costs hundred seconds, making our method is much more efficient.
6.3 Discussion on the Robustness of Search
The robustness has been a critical concern in the differentiable archi- tecture search community since Zela
et al. 45 observed a performance collapse that DARTS tends to yield degenerate architectures, which es- pecially prefers the slip-connections with the search progressing. Similar to DARTS-PP we also focus on the operation selection part to explain the failure of DARTS. Figure 3 presents several architectures by DARTS with our IM different search spaces. Apart from MAS-Bench-22 we also consider several tool search spaces (S1-S4) proposed by (45). which are specifically designed to verify the ro- bustness of differentiable NAS meth- ods. As shown in Figure 3 DARTS-IM can find more meaningful architectures in different spaces. For example, DARTS fails dramatically in most spaces that only selects skip-comnection for all edges, while DARTS-IM can find architecture with 5 convolutions in NAS- HAS-Bench-201, and 6 and 8 convolutions in SI and S2.
k0 30
29.2 36
(a) MAS-BENCH-AN 201
(b) S1
(c) DARTS
(d) S2
Figure 3: Searched architectures on different search spaces.
8

---

6.4 Discussion at Non-Convergence
As discussed in Section 4 our influ- ential magnitude is derived when in the optimum, with leveraging different methods to approximate the IHVPs. In this subsection, we an- alyze whether the proposed influen- tial magnitude is still effective to find important operations when 0 is not in the optimum. Figure 4 tracked the performance of searched architec- ture in each epoch during the search with Sherman-More Morrison formula. As shown, our influential magnitude IM still effective when 0 not in the optimum, while which is getting more stable with the supernet training. Specifically, as shown Figure C (a) and (b), our ZM with the different N are both effective, implying that our method is sufficiently informative for the operation selection even under different approximation noises.
Caech
Eoach
(a) N
(b) N 30
Figure 4: Track the architectures during search on NAS- Bench-201 with
under different N.
More interesting, our DMRTS-IM under Sherman Morrissn formula with N=1 in Figure means VoRVoCT that we simply approximate the inverse H 17 (1 1/ 1 1+. VoL v.C oc A that A-1
is diagonal matrix that Hμ eV, eV L), which is also called the diagonal approximation of the inverse Hessian. As shown, with roughly approximated second-order information, Eq. (7) also help DARTS-IM IM to find more important operations compared with existing heuristic methods.
6.5 Discussion the Limitations in Practice
Although our influential magnitude provides theory-driven and concise solution for the operation selection in DARTS, we consider several assumptions and approximations for the practical imple- mentation. For example, Basu al. 4 [ pointed out that the second-order influence values still underestimated the true group influence values the deep neural networks, while they also observed the correlation marginally improves with the number of parameters in group and the second-order influence function generally outperforms the first-order. Fortunately, this paper considers the whole parameters in the supernet, which helps the second-order influence function reach its potential.
The approximation of IHVPs requires the conditions that the Hessian matrix is positive definite 29 or the empirical Fisher can replace the true Fisher matrix [14) and the supernet weight 6* is global minimum of the empirical risk, while which in practice, are hard to hold. In the calculation _ of v Zoog this paper also follows DARTS that considers the finite difference approximation for practical calculation. These approximations and assumptions may bring errors for the practical calculation, while empirical results verified that our influential magnitude is sufficiently informative for the operation selection in DARTS.
7 Conclusion and Future Work
This paper focuses on the operation selection, which is essential part while with less attention in the differentiable architecture search. Rather than considering heuristics, this paper introduces the influence functions theoretically reveal the candidate operation's 's importance through approximating its influence on the supernet. By leveraging the Taylor's approximation, we gracefully interpret how the validation performance changes during the discretization in DARTS and show that the operation strength is not only related to the magnitude but also the second-order information, where an influential magnitude is accordingly devised for the architecture selection. We based our framework on DARTS and extensive experimental results verified the proposed influential magnitude can be practically used operation selection to avoid failures differentiable architecture search. Developing more accurate influential magnitude for architecture search or leveraging the training dynamics 20 to reveal the operation influence in the early training and also extending influential magnitude to other bi-level
optimization problems 21 28 29 e.g., network pruning (28), are among directions for future work.

---

Acknowledgments and Disclosure of Funding
This work was partially supported by Independent Research Fund Denmark under agreements 8022- 00246B and 0048-00038B, the VILLUM FONDEN under agreement 34328, and the Innovation Fund Denmark centre, DIREC.
References
[1] N. Agarwal, B. Bullins, and E. Hazan. Second-order stochastic optimization in linear time. stat, 1050:15, 2016.
[2] A. Alaa and M. Van Der Schaar. Validating causal inference models via influence functions. In International Conference Machine Learning, pages 191 201. PMLR, 2019.
[3] S.-L. Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-276, 1998.
[4] S. Basu, X. You, and S. Feizi. On second-order group influence functions for black-box predictions. In International Conference on Machine Learning, pages 715-724, PMLR, 2020.
[5] S. Basu, P. Pope, and S. Feizi. Influence functions deep learning fragile. In International Conference on Learning Representations, 2021.
[6] F. Casale, Gordon, and N. Fusi. Probabilistic neural architecture search. arviv: Ntw:/992.05.2 16, 2019.
arXiv preprint
[7] X. Chen and C.-J. Hsieh. Stabilizing differentiable architecture search via perturbation- regularization. In International conference on machine learning, pages 1554-1565. PMLR, 2020.
[8] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235- 222,)26,,,666..... 2007.
[9] N. Couellan and W. Wang. On the convergence of stochastic bi-level gradient methods. Optimization, 2016.
[10] X. Dong and Y. Yang. Searching for robust neural architecture in four gpu hours. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pages 1761-1770, 2019.
[11] X. Dong and Y. Yang. One-shot neural architecture search via self-evaluated template network. In Proceedings of IEEE International Conference on Computer Vision, pages 3681-3690, 2019.
[12] X. Dong and Y. Yang. Nas-bench-2011 Extending the scope of reproducible neural architecture search. International Conference on Learning Representations, 2020.
[13] L. Franceschi, Frasconi, Salzo, R. Grazzi, M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[14] E. Frantar, E. Kurtic, and D. Alistarh. M-fac: Efficient matrix free approximations of second-order information. Advances in Neural Information Processing Systems, 34, 2021.
[15] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv: arXiv:1802.00 1e0..02022..2.... 2018.
arXiv preprint
[16] R. Grazzi, L. Franceschi, M. Pontil, and Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748-375 -7588. PMLR, 2020.
[17] R. Grazzi, M. Pontil, and S. Salzo. Convergence properties of stochastic hypergradients. In International Conference on Artificial Intelligence and Statistics, pages 3826-3834. PMLR, 2021.
[18] F. R. Hampel. The influence curve and its role robust estimation. Journal of the american statistical association, 69)34)))83,333,, 1974.
[19] B. Hassibi and D. Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neurud information processing systems, 5, 1992.
[20] H. He and W. J. Su. The local elasticity of neural networks. In International Conference on Learning Representations, 2020.
10

---

[21] W. Jin, Y. Ma. X. Liu, X. Tang, S. Wang, and J. Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 66-74, 2020.
[22] P. W. Koh and Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pages 1885-1894. PMIR, 2017.
[23] F. Kunstmer, P. Hennig, and L. Balles. Limitations of the empirical fisher approximation for natural gradient descent. Advances in neural information processing systems, 32, 2019.
[24] N. Lee, T. Ajanthan, and P. Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations. 2019.
[25] N. Lee, T. Ajanthan, S. Gould, and P. H. Torr A signal propagation perspective for pruning neural networks at initialization. In International Conference Learning Representations, 2020.
[26] L. Li and A. Talwalkar. Random search and reproducibility for neural architecture search. arXiv preprint arXiv: 1902.07638, 2019.
[27] H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations, 2019.
[28] L. Liu, S. Zhang, Kuang. Zhou, J. Xue, X. Wang. Y. Chen, Yang. Q. Liao, and W. Zhang. Group fisher pruning for practical network compression. In International Conference on Machine Learning, pages 7021-70323 PMLR, 2021.
[29] J. Lorraine, P. Vicol, and D. Duvenaud, Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[30] K. Lu, Z. Wang, P. Mardziel, and A. Datta, Influence patterns for explaining information flow in hert. Advances in Neural Information Processing Systems, 34, 2021.
[31] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through reversible learning. In International conference on machine learning, pages 21 2112-2222. PMLR, 2015.
[32] F. Pedregosa. Hyperparameter optimization with approximate gradient. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, pages 737-746, 2016.
[33] H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean. Efficient neural architecture search via parameter sharing. In International Conference Machine Learning, pages 4092-4101, 2018.
[34] E. Real, A. Aggarwal, Y. Huang, and Q V. Le. Regularized evolution for image classifier architecture search. In Proceedings the aaai conference on artificial intelligence, volume 33, pages 4789-4789, 2019.
[35] P. Ren, Y. Xiao, X. Chang, P.- Huang, Z. Li, X. Chen, and X. Wang A comprehensive survey of neural architecture search: Challenges and solutions. arXiv preprint arXiv:2006.0290 2020.
[36] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated back- proppaapaoationn for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[37] S. P. Singh and D. Alistarh. Woodfisher: Efficient recond-orde approximation for neural network compression. Advances in Neural Information Processing Systems, 33:18098 18108811999 2020.
[38] V. Thomas, F. Pedregosa, B. Merriënboer, P.-A. Manzagol, Y. Bengio, and N. Le Roux. On the interplay between noise and curvature and its effect on optimization and generalization. In International Conference on Artificial Intelligence and Statistics, pages 3503-3513. PMLR, 2020.
[39] C. Wang, G. Zhang, and Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
[40] R. Wang, M. Cheng, X. Chen, X. Tang, and C.-J. Hsieh. Rethinking architecture selection in differentiable nas. In International Conference on Learning Representations, 2021.
[41] X. Wu, D. Zhang, C. Guo, C. He, B. Yang, and C. S. Jensen. Autocts: Automated correlated time series forecasting, Proc. VLDB Endow. 15(4):971-99) 983, 2021.

---

[42] S. Xie, H. Zheng, C. Liu, and L. Lin. Snas: stochastic neural architecture search. In International Conference on Learning Representations, 2019.
[43] Y. Xu, I. Xie, X. Zhang. X. Chen, G.-J. Qi, Q. Tian, and H. Xiong, Pe-darts: Partial channel connections for memory-efficent architecture search. In International Conference on Learning Representations, 2020.
[44] C. Ying, A. Klein, E. Christiansen, E. Real, K. Murphy, and F. Hutter. Nas-bench-101: Towards repro- ducible neural architecture search. In International Conference Machine Learning, pages 7105-7114. PMLR, 2019.
[45] A. Zela, T. Elsken, T. Saikia, Y. Marrakchi, T. Brox, and F. Hutter. Understanding and rohustifying differentiable architecture search. In International Conference on Learning Representations, 2020.
[46] A. Zela, J. Siems, and Hutter. Nas-bench-Ishine Ishotl: Benchmarking and dissecting one-shot neural architecture search. In International Conference on Learning Representations. 2020.
[47] Zhang, Н. Li, Pan, Chang, Z. Ge, and S. Su. Differentiable neural architecture search in equivalent space with exploration enhancement, Advances in Neural Information Processing Systems, 33: 13341-13351, 2020.
[48] M. Zhang, H. Li, S. Pan, X. Chang, and S. Su. Overcoming multi-model forgetting in one-shot nas with diversity maximization. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 7809-7818, 2020.
[49] M. Zhang. H. Li, S. Pan, X. Chang, C. Zhou, Z. Ge, and S. W. Su. One-shot neural architecture search: Maximising diversity to overcome catastrophic forgetting. IEEE Transactions Pattern Analysis and Machine Intelligence, 2020.
[50] M. Zhang, H. Li, S. Pan, T. Liu, and S. Su. One-shot neural architecture search via novelty driven sampling. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20. International Joint Conferenees on Artificial Intelligence Organization, 2020.
[51] Zhang, search with stochastic implicit gradients. In International Conference on Machine Learning. PMLR, 2021.
Pan, X. Chang, E. Abbasnejad, and R. Haffari. idarts: Differentiable architecture
[52] Zhang, S. Pan, Chang, S. Su, J. Hu, G. R. Haffari, and B. Yang. Balenas: Differentiable architecture search via the bayesian learning rule. In Proceedings of the IEEE/CVP Conference on Computer Vision and Pattern Recognition, pages 1 11871-1 1880, 2022.
[53] W. Zhang, Y. Wang, Z. You, M. Cao, P. Huang, J. Shan, Z. Yang, and B. Cui. Rim: Reliable influence-based active learning on graphs. Advances in Neural Information Processing Systems, 34, 2021.
[54] X. Zheng, R. Ji, L. Tang, B. Zhang, J. Liu, and Q. Tian. Multinomial distribution learning for effective neural architecture search. In International Conference on Computer Vision (ICCV), 2019.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
12

---

(d) Did include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're us-
ing/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion offensive content? [N/A]
If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "fNF00I3s7ba", "reviewer": "Reviewer_3tjK", "summary": "The paper studies the architecture selection method for differentiable NAS.\nIt 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.\nThe 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.\nEmpirical 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).", "questions": "1. In Section 6.1, is the search on NAS-Bench-201 conducted on three datasets separately, or just CIFAR-10?\n2. Figure 3 is skewed due to resizing and is hard to read, you may want to modify it.\n3. 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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. 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.\n2. The proposed influence magnitude for measuring operation strength is theoretically justified and intuitive.\n3. Empirical evaluations are overall throughout and solid, with an exception which I will explain in the weakness section.\n\nWeakness:\n\n1. 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.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OZ_1_k24PJm", "reviewer": "Reviewer_D82N", "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.", "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^*)$.\n2. In equation 6, it would be helpful to state that it is assuming that the gradient of the loss equals 0.\n3. 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.\n4. 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.\n5. 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.\n6. 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)?\n7. 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.\n\nI 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. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* The paper is well written, and the idea of using influence-based operation selection is well motivated.\n* 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).\n\nWeaknesses\n* 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.\n* 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.\n* 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.\n* 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. \n* 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.\n\n[1] Wang, R., Cheng, M., Chen, X., Tang, X., & Hsieh, C. J. (2021). Rethinking architecture selection in differentiable NAS. arXiv preprint arXiv:2108.04392.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JFAJgdRFc6o", "reviewer": "Reviewer_8yW8", "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.", "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?  \n- Rather than applying influence functions to the supernet-based NAS, can it be applied to the model-based NAS method?  \n\n[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.", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**  \n- 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.  \n- 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.   \n- 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.  \n- 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.\n\n----------\n**Weaknesses:**  \n- 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.  \n- 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.  \n- 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.   \n- Although this paper nicely presents the operation selection with influential magnitude, some typos also exist.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4-vaRMV1hRa", "reviewer": "Reviewer_pKq9", "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. \n", "questions": "1. Why not compare DARTS-PT in NAS-Bench-1shot1 to make it consistent with other experiments? \n2. How many runs in table2 and table3?\n3. 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? \n", "limitations": "See weaknesses. \n", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Paper is clear and easy to follow.\n+ Give a concretely theoretically interpretation for operation selection in DARTS, which is one of the most popular search algorithm in NAS community. \n+ Search performance by using proposed operation selection method is improved on different search spaces compared to DARTS and its variants . \n+ The proposed method is able to get the stable results in multiple search runs. \n+ Code is available. \n\n- The practical implementation should be based on many assumptions and approximations. \n- The improvement of ImageNet and Cifar10 is marginal. \n- The words/characters in Figure3 is very unclear and hard to understand. \n- Not too much practical.", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept