Robust NAS under adversarial training: benchmark, theory, and beyond
Authors: Yongtao Wu
Fanghui Liu
Carl-Johann Simon-Gabriel
Grigorios Chrysos
Volkan Cevher
Venue: ICLR 2024 poster (2024)
Keywords: neural architecture search
robustness
benchmark
generalization theory
Primary area: datasets and benchmarks
TL;DR: To facilitate the neural architecture search for robust architecture, we release a benchmark under adversarial training and study the robust generalization theory

Abstract: Recent developments in neural architecture search (NAS) emphasize the significance of considering robust architectures against malicious data. However, there is a notable absence of benchmark evaluations and theoretical guarantees for searching these robust architectures, especially when adversarial training is considered. In this work, we aim to address these two challenges, making twofold contributions. First, we release a comprehensive data set that encompasses both clean accuracy and robust accuracy for a vast array of adversarially trained networks from the NAS-Bench-201 search space on image datasets. Then, leveraging the neural tangent kernel (NTK) tool from deep learning theory, we establish a generalization theory for searching architecture in terms of clean accuracy and robust accuracy under multi-objective adversarial training. We firmly believe that our benchmark and theoretical insights will significantly benefit the NAS community through reliable reproducibility, efficient assessment, and theoretical foundation, particularly in the pursuit of robust architectures.

Published as a conference paper at ICLR 2024
ROBUST NAS UNDER ADVERSARIAL TRAINING: BENCH- MARK, THEORY, AND BEYOND
Yongtao Wu LIONS, EPFL
Fanghui Liu"
Carl-Johann Simon-Gabriel
University of Warwick
Mirelo AI
yongtac. wwwepfl.cccmm ch
fanghui. www.warwwck.ac.... ac.
cjsg@mirelo.at
Grigorios G Chrysos"
Volkan Cevher
University of Wisconsin-Madisn chrysos@wise. edu
LIONS, EPFL
volkan.ceeveeeeppl.cc
ABSTRACT
Recent developments in neural architecture search (NAS) emphasize the significance considering robust architectures against malicious data. However, there a notable absence of benchmark evaluations and theoretical guarantees for searching these robust architectures, especially when adversarial training is considered. this work, aim to address these two challenges, making twofold contributions. First, we release a comprehensive data set that encompasses both clean accuracy and robust accuracy for vast array of adversarially trained networks from the NASS- Bench-201 search space on image datasets. Then, leveraging the neural tangent kernel (NTK) tool from deep learning theory, we establish a generalization theory for searching architecture in terms of clean accuracy and robust accuracy under multi-objective adversarial training. We firmly believe that our benchmark and theoretical insights will significantly benefit the NAS community through reliable reproducibility, efficient assessment, and theoretical foundation, particularly in the pursuit of robust architectures.
INTRODUCTION
The success of deep learning can be partly attributed the expert-designed architectures, c.g.. ResNet (He et al. 2016). Vision Transformer (Dosovitskiy et al. 202T), and GPT (Brown et al. 2020), which spurred research in the field of Neural Architecture Search (NAS) (Baker al. 2017 Zoph & Le 2017] Suganuma et al. 2017: Real et al. 2019 Liu et al., 2019). The target of NAS is automate the process of discovering powerful network architectures from search space using well-designed algorithms. This automated approach holds the promise of unveiling highly effec- tive architectures with promising performance that might have been overlooked manually crafted designs (Zela et al. 2020 Wang et al. 2021 Ye et al. 2022).
Nevertheless, merely pursuing architectures with high clean accuracy, the primary target of NAS, is insufficient due to the vulnerability of neural networks to adversarial attacks, where even small perturbations can have detrimental impact on performance (Szegedy et al. 2013). Consequently, there is a growing interest in exploring robust architectures through the lens of NAS (Guo et al.) 2020 Mok al. 2202 Hosseini et al. 2021 |021 Huang et al.) 2022). These approaches aim discover architectures that exhibit both high performance and robustness under existing adversarial training strategics (Goodfellow et al., 2015 Madry et al. 2018).
When studying the topic of robust neural architecture search, find that there are some remaining challenges unsolved both empirically and theoretically. From practical point of view, the accuracy of architecture found by NAS algorithms can be directly evaluated using existing benchmarks through a look-up approach, which significantly facilitates the evolution the NAS community (Ying et al.
"Partially done LIONS, EPFL.
I Partially done at AWS Lablets.
OOur project page available athttps:/ wtt.thhh.....//mobbeeeeeeeeaaaa

---

Published as a conference paper at ICLR 2024
2019; Duan et al. 2021 Dong & Yang 2020 Hirose al. 2021 Zela et. 2022 Bansal et al. 2022
Jung et al. 2023). However, these benchmarks are constructed under standard training, leaving the adversarially ly trained benchmark missing. This requirement is urgent within the NAS community because 1) it would accelerate and standardize the process of delivering robust NAS algorithms (Guo et al., 2020 Mok et al. (02T), since our benchmark can be used as a look-up table; 2) the ranking of robust architectrres shows some inconsistency based on whether adversarial training is involved, as Therefore, one main target of this work is to build a NAS benchmark tailored for adversarial training, which would be beneficial to reliable reproducibility and efficient assessment.
we show in Table [
Beyond the need for benchmark, the theoretical guarantees for architectures obtained through NAS under ad adversarial training remain elusive. Prior literature (Oymak et al.] [021]] Zhuu et al. (022a) establishes the generalization guarantee of the searched architecture under standard training based on neural tangent kernel (NTK) (Jacot et al. 2018). However, when involving adversarial training, it is unclear how to derive NTK under the multi objjetvv objective with standard training and adversarial training. Which NTK(s) s) can be employed to connect and further impact clean accuracy and robust accuracy? These questions pose an intriguing theoretical challenge to the community as well.
Based on our discussions above, we summarize the contributions and insights as follows:
We release the first adversarially trained NAS benchmark called NAS-RobBench-201. This benchmark evaluates the robust performance of architectures within the commonly used NAS-Bench-201 (Dong & Yang 2020) scarch space in NAS community, which includes 6,466 unrepeated network archi- tectures. 107k GPU hours are required to build the benchmark on three datasets (CIFAR- 10/ 100, ImageNet- 16- 16-1 120) under adversarial training. The entire results of all architectures included in the supplementary material and will be public to foster the development of NAS algorithms for robust architecture
We provide a comprehensive assessment of the benchmark, e.g.. the performance of different NAS algorithms, the analysis of selected nodes from top architectures, and the correlation between clean accuracy and robust accuracy. We also test the correlation between various NTK metrics and accuracies, which demonstrates the utility of (TK((s) for architecture search.
We consider general theoretical analysis framework for the searched architecture under multi- objective setting, including standard training and adversarial training, from a broad search space, of Theorem [ Our framework allows for fulle-connected neural networks (FCNNs) and convolutional neural networks (CNNs) with activation function search, skip connection search, and filter size search (in CNNs). Our results indicate that clean accuracy determined by a joint NTK that includes partly a clean NTK and a robust NTK while the robust accuracy is always influenced by a joint NTK with the robust NTK and its "twice" perturbed version For complete theoretical analysis, we provide the estimation of the lower bound of the minimum eigenvalue of such joint NTK, which significantly affects the (robust) generalization performance with guarantees.
By addressing these empirical and theoretical challenges, our benchmark comprehensively evaluates robust architectures under adversarial training for practitioners. Simultaneously. our theory provides a solid foundation for designing robust NAS algorithms. Overall, this work aims contribute to the advancement of NAS, particularly in the realm of robust architecture search, well as broader architecture design.
2 RELATED WORK
In this section, we present a brief summary of the related literature, while comprehensive overview and discussion of our contributions with respect to prior work are deferred to Appendix [B]
Ad Adversarial example and defense. Since the seminal work of Szegedy et al. (2013) illustrated that neural networks are vulnerable to inputs with small perturbations, several approaches have emerged to defend against such attacks (Goodfellow et al., 2015 Madry et al.] [018 Xu et al. 2018 Xie et al. 2019 Zhang et al. 2019 Xiao et al. 2020). Adversarial training (Goodfellow et al. 2015 Madry et al. 2018 of the most effective defense mechanisms that minimizes the empirical training loss based
Wall "clean NTK" the standard NTK w.r.t clean input while "robust NTK" refers to the NTK with adversarial input. The "twice" perturbed version refers the input where adversarial noise is added twice.
2

---

Published as a conference paper at ICLR 2024
#1
#5
#3
3x3 Conv,
1x1 Conv
#2
#6
Zeroize,
Skip connect,
1x1 Avg. pool
#4
Conv +
Cell
x 5
Residual block
Cell
5
Residual block
Cell
x 5
Global avg. pool
Linear
Visualization of the NAS-Bendee 201 search space. Top left: A neural cell with 4 nodes and edges. Top right: 5 predefined operations that can be selected as the edge in the cell. Bottom: Macro structure of each candidate architecture in the benchmark.
Figure 1:
on the adversarial data, which obtained by solving a maximum problem. [Goodfellow (2015) use Fast Gradient Sign Method (FGSM), one-step method, to generate the adversarial data. However, FGSM relies on the lincarization of loss around data points and the resulting model is still vulnerable to other more sophisticated adversaries. Multi-step methods are subsequently proposed to further improve the robustness, e.g., multi-step FGSM (Kurakin et al.) 2018), multi-step PGD (Madry et al. 2018)) To mitigate the effect of papeeeparameters PGD and the overestimation of robustness (Athalye et al.) 2018). [Croce & Hein ( (020b) propose two variants of parameter-free PGD attack, namely, APGDeR and APGDDLR. where CE stands for cross-entree prosspyntropy loss and DLR indicates difference of logits ratio (DLR) loss. Both APGDcE and APGDDLR attacks dynamically adapt the step-size of PGD based on the loss each step. Furthermore, enhance the diversity of robust evaluation, Croce & Hein (2020b) introduce Auto-attack, which is the integration of APGDCE. APGDDLR. Adaptive Boundary Attack (FAB) (Croce & Hein 2020a), and black-box Square Attack (Andriushchenko et al. 2020).
Other methods of generating adversarial examples include L-BFGS (Szegedy et al. 2013). attack (Carlini & Wagner 2017).
C&W
NAS and benchmarks. Over the years, significant strides have been made towards developing NAS
algorithms from various perspectives, c.g., differentiable search with weight sharing (Liu et al. 2019
Zela al.) 2020 Ye et al.) 2022), NTK-based methods (Chen et al. 202 Xu et al. 2021 Mok
et al. 20022] Zhu et al. (022a) Most recent work on NAS for robust architecture belongs to the
first category (Guo et al. 2020 Mok al. 2021). Along with the evolution of NAS algorithms, the
development of NAS benchmarks is also important for an efficient and fair comparison. Regarding
clean accuracy, several tabular benchmarks, e.g., NAS-Bench-UD
(Ying al. 2019), TransNAS- Bench-101 (Duan et al. 2021). NAS-Bench-201 (Dong & Yang 2020) and NAS-Bench-300 (Zela et al.
2022) have been proposed that include the performance under standard training on image classification tasks. More recently, Jung et al. (2023) extend TAS-Bench-225 towards robustness by evaluating the performance WAS-Bench-200 space terms of various attacks. However, all of these benchmarks are under standard training, which motivates us to release the first NAS benchmark that contains the performance under adversarial training.
NTK. Originally proposed by Jacot al. (2018). NTK connects the training dynamics of over- parameterized neural networks to kernel regression. In theory, NTK provides tractable analysis for several phenomena in deep learning. For example, the generalization guarantee of over peremerraeterieed FCNN under standard training has been established in Cao Gu (2019); Zhu et al. (2022a). this work, extend the scope of NTK- generalization guarantee to objectve training, which covers the case of both standard training and adversarial training.
NAS-ROBBENCHA
In this section, first describe the construction of the benchmark, including details search space, datasets, training setup, and evaluation metrics. Next, we present a comprehensive statistical analysis of the built benchmark. More details can be found in the supplementary.
3

---

Published as a conference paper at ICLR 2024
CIFAR-10
CIFAR-100
ImageNet 1o-ttt16-2200
80
60
40
12
Accuracy %
Accuracy %
Accuracy
10-
40
20
10
Oean
FOSM 32255
roD 3255
resM 6/255
PoD. 82355
Glaa
rGsM 3/238
POD. 3233
rGsM 8259
FOD 52555
FGSM 32355
POB 3253
FOSM ar250
PaD arss
Figure 2: Boxplots for both clean and robust accuracy of all 6466 non-isomorphic architectures in the
considered search space. Red line indicates the accuracy of a random guess.
FGJM, ASCS
Architecture ranking
Architecture ranking 2:25
P0D. 5125
FOOML 8225
Frequency
4313
2335
CPAA-10
Accuracy %
Architecture ranking. Clean
Architecture ranking. CIFAR-10
(b) Ranking of different metrics. (a) Distribution of accuracy.
(c) Ranking across datasets.
Figure 3: (a) Distribution of accuracy on CIFAR-10 10. The peak in the distribution of clean accuracy is much more notable than that FGSM and PGD. (b) The architecture ranking on CIFAR- 10 sorted by robust metric and clean metric correlate well for lower ranking (see larger x-axis) but there still exists difference for higher ranking. Both (a) and (b) motivate the NAS for robust architecture in terms of robust accuracy instead of clean accuracy. (c) Architecture ranking of average robust accuracy on 3 datasets, sorted by the average robust accuracy on CIFAR- 10. The architectures present similar performance across different datasets, which motivates transferable NAS under adversarial training.
Table 1:
Spearman coefficient between various accuracies on CIFAR-10 on HAS-RobBench-200 and the benchmark Jfun et al. (2023). Specifically, the first three columns/rows (without *) indicate the clean, PGD (8/255), and FGSM (8/255) accuracies in NAS-Rob -ew-RRoR-Beeeeee 2011 while the last three columns/rows (with** *) indicate the corresponding accuracies in Jung et al. (2023).
Clean
PGD
FGSM
Clean
PGD
FGSM
Clean
1.000
0.985
0.989
0.977
0.313
0.898
PGD
0.985
1.000
0.998
0.970
0.382
0.937
FGSM
0.989
0.998
1.000
0.974
0.371
0.931
Clean
0.977
0.970
0.974
1.000
0.322
0.891
PGD*
0.313
0.382
0.371
0.322
1.000
0.487
FGSM*
0.898
0.937
0.931
0.891
0.487
1.000
3.1 BENCHMARK CONSTRUCTION
Search space. We construct our benchmark based on a commonly-used cell-based search space in the NAS community: NAS-Bench-201 (Dong & Yang) 2020), which consists of 6 edges and operators as depicted Figure [
Each edge can be selected from the following operator: Convolution, Zeroize, Skip connect, I x Average pooling). which results in 56 = 15625 architectures while only 6466 architectures are non-isomorphic. Therefore, we only train and evaluate 6466 architectures.
{3 x Convolution,
Dataset. evaluate each network architecture on (a) CIFAR 10 Krizhevsky et 2009). (b) CIFAR- 100 (Krizhevsky et al. 2009), and (c) 1mageNeet16--1 16-120 (Chrabaszez al. 2017). Both CIFAR-10
4

---

Published as a conference paper at ICLR 2024
60.2
Archilectures ID
Arrrage robust accuracy
2581
60.0
9930
13714
655
1459
5292
9586
2778
Edgoa1
Ed0042
Edge43
Edgea4
Edgoas
Edga46
59.4
Zembe-
Skip
Cone
5x5 Corv
Zemice
Skip
Cone
3x3 Cone
Zonibe
Skip
Cone
3x3 Cone
Zerbbe-
1xt Conu
3x3 Cone
Ave
Zambbe
1xd Cone
3x3 Cone
1el Ave
Zeroic
1xd Cone
3x3 cone
1el Ave-
1el
1el
Figure 4: The operators of cach edge in the top-10 architectures (average robust accuracy) on NAS-
RobBench-201. The definition of edge number (#1~##6) and operators are illustrated in Figure
and CIFAR- 100 contain 60,000 RGB images of resolution 32 32, where 50,000 images are in the training set and 10,000 D00 images are in the test set. Each image in CIFAR- 10 is annotated with out of the 10 categories while there are 100 categories in CIFAR-100. ImageNet- 1--fee----121 16-120 is variant of ImageNet that down-samples the images to resolution 16 16 and selects images within the classes [1,120]. In total, there are 151,700 700 images in the training set and 6,000 images in the set. Data augmentation is applied for the training set. On CIFAR-10 and LIFAR-100, we apply a random crop for the original patch with 4 pixels padding on the border, random flip with a probability of 0.5, and standard normalization. On ImageNet- 16- 120, we apply similar augmentations via random crop with 2 pixels padding. The data is normalized before the attack, following the setup in Zhang et al. 2019);
Rice et al. 2020).
Training procedure. We adopt standard adversarial training setup via mini-batch SGD with step-size of 0.05, momentum of 0.9, weight decay of 10-1, and batch size of 256. We train each network for 50 epochs where one-cycle step-size schedule with maximum step-size 0.1 (Smith & Topin 2019), which is proposed for faster convergence. Each run is repeated for 3 different seeds. Regarding the adversarial attack during training, we follow a common setting, i.e., 7 steps of projected gradient descent (PGD) with step-size 2/255 and perturbation radius p = 8/255 (Madry et al. 201 20. We apply the same setup for all of the aforementioned datasets. In total, we adversarially train and evaluate 6466 x x 3 z 58k archifectures by a number of NVIDIA T4 Tensor Core GPUs. One seed for one dataset consumes approximately 34 hours on 350 GPUs. Consequently. 3 datasets and 3 seeds take around 34 350 x 3 3 107k GPU hours.
Evaluation metrics. We evaluate the clean accuracy and robust accuracy of each architecture after train- ing. Specifically, we measure the robust accuracy based on fast gradient sign method (FGSM) (Goodfel) low et al. 2015) and PGD attack with Eoo constraint attack with perturbation radius o {3/255, 225,8//55 5/255 For PGD attack, we adopt 20 steps with step-size 2.5 p/ p/20. Additionally, we evaluate each architec- ture under AutoAttack with perturbation radius p = 8/255.
3.2 STATISTICS OF THE BENCHMARK
Overall preview of the benchmark. In F we show the boxplots of the clean accuracy and robust accuracy of all architectures the search space, respectively. Notice that there exists non- nog-neglii gap between the performance of different architectures, e.g., ranging from 40%~ ~ 70% accuracy under FGSM attack on CIFAR-10. Therefore, designing the architecture holds immense significance given the wide spectrum of achievable accuracy values. In Figure [3| plot the distribution of the clean accuracy and robust accuracy on CIFAR- 10 in the proposed NAS- -ob-RRoc--enBOO 20 We observe that the distribution of FGSM accuracy and PGD accuracy similar while the peak in the distribution of clean accuracy is much more notable than that of FGSM and PGD. Overall, the architecture ranking sorted by robust metric and clean metric correlate well, shown in Figure 3b
Effect of operators selection on robustness. To see the impact of operators in robust architecture design, in Figure 4 present the selected operators each edge of the top- 10 architectures in
5

---

Published as a conference paper at ICLR 2024
Table 2: Result of different NAS algorithms on the proposed NAS-RobBench-200 20 "Optimal" refers to the architecture with the highest average robust accuracy among the benchmark. "Attack scheme" in the first column indicates how the accuracy is measured during the searching phase these baseline methods.
FGSM
PGD
FGSM (8/255)
PGD
Attack scheme
Method
Clean
(3/255)
(3/255)
(8/255)
Optimal
0.794
0.698
0.692
0.537
0.482
Regularized Evolution
0.791
0.693
0.688
0,530
0.476
Clean
Random Search
0.779
0,682
0.676
0.520
0.470
Local Search
0.796
0.697
0.692
0.533
0.478
Regularized Evolution
0.790
0.693
0.688
0.532
0.478
FGSM (8/255)
Random Search
0.774
0.679
0.674
0.521
0.471
Local Search
0.794
0.695
0.689
0.535
0.481
Regularized Evolution
0.789
0.692
0.686
0,531
0,478
PGD (8/255)
Random Search
0.771
0.676
0.671
0.520
0.471
Local Search
0.794
0.695
0.689
0.535
0.481
CIFAR-10 dataset. The top-10 criterion is the average robust aceuracy, which the mean of all robust metrics mentioned in S.ction Overall, these top architectures have similar operator selections at each edge. We can see there exists a frequently selected operator for each edge. For instance, the 3 x convolution operation appears be the best choice for the majority of edges, except for edge 4, where the skip-connection operation demonstrates its optimality.
Architecture ranking across different datasets. Figure 3e depicts the architecture ranking based on the average robust accuracy across (IFAR-10/100 and ImageNet- 16. The result reveals a high correlation across various datasets, thereby inspiring the exploration of searching on smaller dataset to find a robust architecture for larger datasets.
Comparison with the existing benchmark (Jung et al.) 2023). The closest benchmark ours is built by Jung et al. (2023), where the robust evaluation of each architecture under standard training is given. In Table underscores the significance of adversarial training within our benchmark. Specifically, it suggests that employing Jungoggnnnnnggggoooooooo Jung al. (2023) identify resilient architecture may not guarantee its robustness under adversarial training. Moreover, in Fi of the appendix, we can see notable difference between these two benchmarks terms of top architectures id and selected nodes.
present the Spearman coefficient among different accuracies. The observation
NAS algorithms on the benchmark. Let us illustrate how to use the proposed NAS MAS--RooBench-222 for NAS algorithms. As an example, we test several NAS algorithms on CIFAR- 10. The search-based NAS algorithms include regularized evolution (Real et al. 2019), local search (White et al.) 2021 and random search (Li & Talwalkar 2020). We run each algorithm 100 times with 150 queries and report the mean accuracy in Table We can observe that by searching the robust metrics, c.g., FGSM and PGD, these methods are able to find more robust architecture than using clean accuracy metrics. Additionally, local search performs better than other methods. Evaluation results
NAS approaches including differentiable search approaches (Liu et al. 2019 Mok et 2021) and train-free
approaches (Xu et al., 20221] Zhu et al. 2022a Shu al. 2022 Mellor al. 2021 deferred to Table of the appendix.
ROBUST GENERALIZATION GUARANTEES UNDER NAS
Till now, we have built MAAS-RobBench-20 to search robust architectures under adversarial training. To expedite the search process, NTK-based NAS algorithms allow for a train-free style in which neural architectures can be initially screened based on the minimum eigenvalue of NTK as well as its variants, e.g., Chen et al. (202 bb; Xu et al. a (2021 1 Mok et al. (2022) Zhu et al. (2022a). Admittedly, it's worth noting that these methods build upon early analysis on FCN Ns under standard training within the learning theory community (Du al.) 2019c Cao & Gu 2019 Lee et al. 2019). Consequently, our subsequent theoretical results aim to provide a solid groundwork for the development of NTK- based robust NAS algorithms. Below, the problem setting is introduced in Section The (robust)

---

Published as a conference paper at ICLR 2024
generalization guarantees of FCNNs as well as CNNs present in Section for the notations can be found in Appendix A
4.2 Detailed definitions
4.1 PROBLEM SETTING
We consider a search space suitable for residual FCNNS and residual CNNs. To be specific, the class of L-layer (L 3) residual FCNN with input E Rd and output f(x W) R is defined as follows:
1 fi= L o (a 2515--1,
fi = (W()) (x),
(1)
fL = (WI.
f(x,W)=
where Wi Rmxdd Wi E Rmxm .l=.n,,12........
and wt Rm are learnable weights under Gaussian
initialization i.e., W w(()) (65) ~.(001/m) for L [L] This is the typical NTK initialization to ensure the convergence of the NTK (Allen (Allen-Zhu
-hhu et al. 2019 Zhu al. 2022a). We use W := : (W.....wr.) W to represent the collection of all weights. The binary parameter E {0,1) determines whether skip connection is used and o)(.) represents an activation function in the 1 layer. Similarly, we define I--layer (T. 2 3) residual CNNs with input X E Rdxp, where d denotes the input channels and represents the pixels, and output f(X, W) e follows:
= (W
F L (W
251SL-1,
F1 (W, Fi-I.
1(X =
where W1 E Rexxxxd W.ERAxXm 1 I....,I--1 and WL E ER"Xp are learnable weights with m channels and filter size. We define the convolutional operator between X and Wi as:
(W1* + X
W (u.see) (mgitu "t for iE
k=Iv=1
where we use zero-padding, i.e., (e.e) =0 for e or e>p.
Firstly, we introduce the following two standard assumptions to establish the theoretical result.
Assumption 1 (Normalization of inputs). We assume the input space of FCNN is: X' S fx e Rd:
|| Similarly, the input space of CNN is: X X E RdxXp || ||||= 11.
Assumption 2 (Lipschitz of activation functions). We assume there exist two positive constants Ci,Lip and CLip such that |o (0) S Ct S CLip with LE [L] for any z,z ER:
( Ct..i.ll- CCpplR=''
where Ciip is the maximum value of the Lipschitz constants of all activation fianctions in the networks.
Remarks:
a) The first assumption is standard in deep learning theory and attainable in practice as we always scale the input (Zhang al. 2020). b) The second assumption covers range of commonly used activation functions, e.g., ReLU, LeakyReLU,, or sigmoid (Du et al. 2019a).
Based our description, the search space for the class of FCNNs and CNNs includes: a) Activation function search: any activation function a that satisfies Assumption 2 b) Skip connection search: whether aq is
one. c) Convolutional filter size search: the value of
Below we describe the adversarial training of FCNN while the corresponding one for CNN can be defined in the way by changing the input as X.
Definition 1 (p-Bounded adversary). An adversary :p: W is p-bounded for p> if satisfies: Ap(2, W) E (ar,p). We denote by A the worst-case p-bounded adversary given a loss function é: A W) := mergmaxeBB...pp (f (t.))..
(a. W) by omitting the label Without loss of generality, we restrict our input æ as well as its perturbation set ((x,p) within the surface of the unit ball S:= {ar EIR: | 1e]1==1 (Gao et al. 2019).
For notational simplicity, simplify the above notations as Ap ( W) and A²
7

---

Published as a conference paper at ICLR 2024
We employ the cross-entropy loss f(2): := + cxp( for training. We consider the following multi-objective function involving with the standard training loss Lelean (W) under empirical risk minimization and adversarial training loss Crobust (W) with adversary in Definition
N
min (1-3) W
CCclnn((W)
g=obbat (W)
where the regularization parameter B E [0, adversarial training. The case refers to the standard training and B corresponds to the adversarial training. Based on description, the neural network training by stochastic gradient descent (SGD) with a step-size y is shown in Algorithm
is for trade-off between the standard training and
4.2 GENERALIZATION BOUNDS
NTK plays an important role in understanding the generalization of neural networks (Jacot et al. 20188) Specifically, the NTK is defined as the inner product of the network Jacobian w.r.t the weights at initialization with infinite width, i.e., )
/a, . af(e).WDl))
(ive((W) (vee(WW) To present the
generalization theory, let us denote the NTK matrix for clean accuracy as:
KAn1 = (1- 3) K 3(1 (3
8 K,,
where K((..) = K(a,e is called the clean NTK, K, (1.)))
(z, W(l)) )) is the cross NTK, and is the robust NTK, for any i.j E [N]. Similarly, denote the K = ((,,(,,, ,,A w(l))
k =
NTK for robust accuracy
= 3) K (1- 20 K + K2p-
(5)
where the robust NTK K, has been defined in Eq. (4). K K-(l.)) k W()),,a;) and K((
2p
w under "twice" perturbation. Note that the formulation of "twice" perturbation allows seeking a perturbed point outside the radius of indicating stronger adversarial data used. Such perturbation is essentially different from doubling the step size under a single Interestingly, such scheme has the benefit of avoiding catastrophic overfitting (de Jorge et al. 2022). Accordingly, we have the following theorem on generalization bounds for clean/robust accuracy with the proof deferred to Appendix C
(.) for i,j E [N]. with á; A WL)),
Theorem (Generalization bound of FCNN by NAS), Denote the expected clean 0-1 loss as C (W) E(e.vi [1 {uf W)<03], and expected robust 0-1 loss as Crobust(Wi (W) E(m.a) [1
W), W) <O]] Consider the residual FCNNs in Eq. (I) by activation function search and skip connection search, under Assumption Tand2 CLip- Ifone runs Algorithm with
a step-size 7 = min(y] (Kan)-1y. (Ka))-"y)) / Cripe morm/NN)) N) for small enough abso- lute constant and width m m m", where m depends on LLip ) &..)) then for any p 1, with probability least over the randomness of WIl, we obtain:
I.2 K
log(1/8)
Ew (Colean (W))
+0
N
N
(6)
E E (Cr (W)SO
LPy
K
y
+0
log(1/8)
where Amin (-) indicates the minimum eigenvalue the NTK matrix. the expectation the LHS is taken over the uniform sample of W from [Wil Bo.!'!...WW!baa W[N],, }, as illustrated in Algorithm
Remarks: a) By courant minimax principle (Golub & Van Loan
1996).
further have
y Kanl -y S y [Kan) and y k R_ Amii (an)
Cao & Gu 2019 9 Zhu et al. (002b) prove
(Ka))
8

---

Published as a conference paper at ICLR 2024
Algorithm 1: Multi- adversarial training with stochastic gradient descent
Input: data distribution 2) adversary Ap. step size y, iteration N, initialized weight Will,,
for
to do
Sample (2::3/) from D. W will
end for Randomly choose W uniformly from {Wil, wI..)
Output: W.
for FCNN under standard training that the standard generalization error is affected by only Amin (K) As comparison, result exhibits that under multi-objective training, the generalization error is controlled by a mixed kernel Kall with regularization factor B3. We can recover their result by taking 0 i.e., standard training under the clean NTK. Taking 3 = falls in the case of adversarial training with robust NTK. c) Our theory demonstrates that the clean accuracy is affected by both the clean NTK and robust NTK, but the robust generalization bound influenced by the robust NTK and its "twice" perturbation version.
Here we extend our generalization bound CNN with proof postponed to Appendix
Corollary 1. Consider the residual CNN defined in Eq. (2. If one applies Algorithm min(y" (Kau)= y, y (Kau) ) 1)/(( ( MVN for
7
with a step-size ? some small enough absolute constant v and the width m 2 m², where m depends on (N, L.,.P.PK. CLip, Amin , Amiu K au), au),,,n B.p,8), then under Assumption and 2 for any p S 1, with probubility at least 1- 6, one has the generalization result as Eq. (6)
Remarks: Notice that the filter size affects the step-size and the required prrametramttinnnaioonnn condition. A larger filter size enables larger siep-sizes to achieve faster convergence rate, which aligns with practical insights (Ding et al. 2022
4.3 CORRELATION BETWEEN NTK AND ACCURACY ON MAS-ROBBENCH-20
In Figure plot the Spearman corre- lation between different NTK scores and various accuracy metries. Specifically, we
0.527
0.533
0.540
0.537
0.549
use adversarial data with PGD attack to
FOSH
1255
0,546
0.552
0.559
0.556
0.568
construct the kernel K, defined Eq. 4 Then, to efficiently compute Amin. we es- timate by Frobenius norm as Xu et al. (2021), and we simply name it NTK- score. Specifically, we focus on distinct NTK variants, including clean NTK. robust NTKs with E 255, /255), and the corresponding robust twice NTKs. Regard- ing the robust twice NTK, we first perform PGD attack the image data generate the adversarial data, and then we perform the same attack on this adversarial data again and use it to construct the NTK. Our findings reveal that robust NTT's ex- hibit notably stronger correlation when compared to standard NTK under adversar- ial training. More interestingly, observe that the correlation is increasing for met- rics with larger perturbation. Such findings persist when examining NTKs with FGSM attack, elaborate in Appendix
ASD
0.543
0.550
0.556
0.553
0.565
Accuracy
APND
0.541
0.548
0.554
0.551
0.564
FISH
0.601
0.608
0.614
0.611
0.622
PGD
0.598
0.604
0.610
0.608
0.619
APGO
0.593
0.599
0.605
0.602
0.615
KNAS
PGb P 3/255
AGD, p
2
NTK score
Figure 5: Spearman coefficient between NTK-scores and various metrics. Labels with 2p in the x-axis indicate the scores w.r.t the robust twice NTK while labels with indicates the score w.r.t the robust NTK.

---

Published as a conference paper at ICLR 2024
5 CONCLUSION
In this paper, to facilitate the research of the NAS community, we release NAS-RobBench- that includes the robust evaluation result 6466 architectures image datasets under adversarial training. Furthermore, study the robust generalization guarantee of both FCNN and CNN for NAS. Our result reveals how various NTKs can affect the robustness of neural networks, which can motivate new designs of robust NAS approaches. The first limitation is that our benchmark and theoretical results do not explore the cutting-edge (vision) Transformers. Additionally, our NTK K-based analysis studies the neural network in the linear regime, which can not fully explain its success in practice (Allen-Zhu et al.) 2019) Yang & Hu 2021). Nevertheless, we believe both our benchmark and theoretical analysis can be useful for practitioners in exploring robust architectures.
ACKNOWLEDGEMENT
We thank the reviewers for their constructive feedback. We are grateful to Kailash Budhathoki from Amazon for the assistance. This work has received funding from the Swiss National Science Foundation (SNSF) under grant number 200021 20501 This work was supported by Hasler Foundation Program: Hasler Responsible Al (project number 21043). Corresponding author: Fanghui Liu.
ETHICS STATEMENT
On hand, in the pursuit of facilitating innovation in robust neural architecture design, we build benchmark by using around 107k GPU hours. We acknowledge that such a substantial computational footprint has environmental consequences, e.g., energy consumption and carbon emissions. On the other hand, the core target of robust NAS is to guarantee that Al models excel not only accuracy but also in robustness towards malicious data. Therefore, anticipate positive societal consequences stemming from our research efforts.
REPRODUCIBILITY STATEMENT
Details on the construction the benchmark can be found in Section 3.1 of search space, dataset, and hyperparameters setting. Furthermore, in the supplementary material, we provide the evaluation results of all architectures in the proposed benchmark. The code and the pre-trained weight will be publicly released after the paper's acceptance. Regarding the theoretical result, all the proof's can be found Appendix too
including the description
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. In International Conference on Machine Learning (ICML), 2019.
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficieet black-box adversarial attack via random search. In European Conference Computer Vision (ECCV), pp. 484-501. Springer, 2020.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov. Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets small-data tasks. In International Conference on Learning Representations (ICLR), 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning (ICML), 2018.
Bowen Baker, Otkrist Gupta. Nikhil Naik, and Ramesh Raskar. Designing neural network architectures using reinforcement learning. In International Conference on Learning Representations (ICLR), 2017.
10

---

Published as a conference paper at ICLR 2024
Archit Bansal, Danny Stoll, Maciej Janowski, Arber Zela, and Frank Hutter. Jahs-bench-200. A foundation for research on joint architecture and hyperparameter search. In Advances in neural information processing systems (NeurIPS), 2022.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. Advances in neural information processing systems (NeurIPS), 2019.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems (NeurIPS), 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems (NeurIPS), 2019.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning, arXiv preprint arXiv:1912.01195 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks, In 2017 ieee symposium on security and privacy (sp), pp- 39-57. leee, 2017.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. In International Conference on Learning Representations (ICLR), 2021.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems (NeurIPS), 2019.
Moulik Choraria, Leello Tadesse Dadi, Grigorios Chrysos, Julien Mairal, and Volkan Cevher. The spec- tral bias of polynomial neural networks. International Conference on Learning Representations (ICLR), 2022.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. downsampled variant of imagenet as an alternative to the cifar datasets, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness adversarial examples. In International Conference on Machine
Learning (ICML), 2017.
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning (ICML), 2020a.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning (ICML), 2020b.
Pau de Jorge, Adel Bibi, Riccardo Volpi, Amartya Sanyal, Philip Torr, Grégory Rogez, and Puncet K. Dokania. Make some noise: Reliable and efficient single- step adversarial training. In Advances in neural information processing systems (NeurIPS), 2022.
Xiaohan Ding, Xiangyu Zhang, Jungong Han, and Guiguang Ding. Scaling up your kernels to 31x31: Revisiting large kernel design in cnns. In Conference on Computer Vision and Puttern Recognition (CVPR), 2022.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope reproducible neural architecture search. In International Conference Learning Representations (ICLR), 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations (ICLR), 2021.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning (ICMI), 2019a.
11

---

Published as a conference paper at ICLR 2024
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, Advances in neural information processing systems (NeurIPS), 2019b.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameteriied neural networks. In International Conference on Learning Representations (ICLR), 2019c.
Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang, Tong Zhang, and Zhenguo Li. meassna--bench-- 101: Improving transferability and generalizability of cross-task neural architecture search. In Conference on Computer Vision and Puttern Recognition (CVPR), 2021.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. In Advances in neural information processing systems (NeurIPS), 2019.
Xitong Gao, Cheng-Zhong Xu, et al. Mora: Improving ensemble robustmess evaluation with model reweighing attack. Advances in Neural Information Processing Systems, 2022.
Gene Golub and Charles F. Van Loan. Matrix Computations (3rd Ed.). 1996.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations (ICLR), 2015.
Minghao Guo, Yuzhe Yang, Rui Xu, Ziwei Liu, and Dahua Lin. When nas meets robustness: In search of robust architectures against adversarial attacks. In Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual leamingg for recognition In Conference on Computer Vision and Pattern Recognition 2016.
Zhezhi He, Adnan Siraj Rakin, and Deliang Fan. Parametric noise injection: Trainable randomness to improve deep neural network robustness against adversarial attack. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. pp. 588-597, 2019.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. In International Conference on Learning Representations (ICLR), 2019.
Yoichi Hirose, Nozomu Yoshinari, and Shinichi Shirakawa. Nas-hpo-bench-iit A benchmark dataset on joint optimization of convolutional neural network architecture and training hyperparameters. In Asian Conference on Machine Learning. 2021.
Ramtin Hosseini, Xingyi Yang, and Pengtao Xie. Dsrna: Differentiable search of robust neural architectures. In Conference on Computer Vision and Pattern Recognition pp. 2196-6208 2021.
Hanxun Huang, Yisen Wang, Sarah Erfani, Quanquan Gu, James Bailey, and Xingjun Ma. Exploring architectural ingredients of adversarially robust deep neural networks. In Advances in neural information processing systems (NeurIPS), 2021.
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks generalize better than deep feedforward networks?-a neural tangent kernel perspective. Advances in neural information processing systems (NeurIPS), 2020.
Shihua Huang, Zhichao Lu, Kalyanmoy Deb, and Vishnu Naresh Boddeti. Revisiting residual networks for adversarial robustness: An architectural perspective. arXiv preprint arXiv:22/2. 2022.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and general- ization in neural networks. In S. Bengio, H. Wallach, H. Larochelle. K. Grauman, N. Cesa- Bianch,, and R. Garnett (eds.), Advances in neural information processing systems (NeurIPS), 2018.
Steffen Jung, Jovita Lukasik, and Margret Keuper. Neural architecture design and robustness: A dataset. In International Conference Learning Representations (ICIR), 2023.
12

---

Published as a conference paper at ICLR 2024
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. In Technical report, 2009.
Souvik Kundu, Mahdi Nazemi, Peter A Beerel, and Massoud Pedram. Dar: A tunable robust pruning framework through dynamic network rewiring of dnns. In Proceedings of the 26th Asia and South Pacific Design Automation Conference, pp. 344-350, 2021.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In Artificial intelligence safety and security, 2018.
Jaehoon Lee, Lechao Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems (NeurIPS), 2019.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley, Neural architecture search without training. In International Conference Machine Learning (ICML), 2021.
Jisoo Mok, Byunggook Na, Hyeokjun Choe, and Sungroh Yoon. Advrush: Searching for adversarially robust neural architectures. In International Conference on Computer Vision (ICCV), 2021.
Jisoo Mok, Byunggook Na, Ji-Hoon Kim, Dongyoon Han, and Sungroh Yoon. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training? Conference on Computer Vision and Puttern Recognition (CVPR), 2022.
Quynh N Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Advances in neural information processing systems (NeurIPS), 2020.
Samet Oymak, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guarantees for neural archi- tecture search with vain-validation split. In International Conference on Machine Learning, pp- 8291-8301, 2021.
Adityanarayanan Radhakrishnan, George Stefanakis, Mikhail Belkin, and Caroline Uhler. Simple, fast. and flexible framework for matrix completion with infinite width neural networks. Proceedings of the National Academy of Sciences, 119(16) 1,5041 19, 2022.
Estehan Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc V Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In International Conference Machine Learning (ICML), 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In AAAI Conference on Artificial Intelligence, 2019.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 8093-8104. PMIRR, 2020.
Andrew Ross and Finale Doshi-Vele Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. In AAAI Conference on Artificial Intelligence, 2018.
Yao Shu, Shaofeng Cai. Zhongxiang Dai, Beng Chin Ooi, and Bryan Kian Hsiang Low. Nasi: Label-and data-agnostic neural architecture search at initialization. International Conference on Learning Reprexentations (ICLR), 2022.
13

---

Published as a conference paper at ICLR 2024
Leslie N Smith and Nicholay Topin. coner-eonee Very fast training of neural networks using large learning rates. In Artificial intelligence and machine learning for applications, volume 1 11006, pp. 369-386. SPIE, 2019.
operations
Masanori Suganuma, Shinichi Shirakawa, and Tomoharu Nagao. A genetic programming approach to designing convolutional neural network architectures. In Proceedings of the genetic and evolutionary computation conference, 2017.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier features let networks learn high frequency functions in low dimensional domains. Advances in Neural Information Processing Systems, 33:7537-7547, 2020.
Roman Vershynin. Introduction to the non-asymptotic analyiss of random matrices, pp. 210-268. Cambridge University Press, 2012. doi: 10.1017/CB80978511 1e0.541119938800000 0006.
Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsich. Rethinking architecture selection in differentiable nas. In International Conference on Learning Representations (ICLR), 2021.
Yihan Wang, Zhouxing Shi, Quanquan Gu, and Cho-Jui Hsich. On the convergence of certified robust training with interval bound propagation. In International Conference on Learning Representations (ICLR), 2022.
Colin White, Sam Nolen, and Yash Savani. Exploring the loss landscape in neural architecture search. In Uncertainty in Artificial Intelligence, 2021.
Chang Xiao, Peilin Zhong, and Changxi Zheng. Enhancing adversarial defense by k-winners-take-a In International Conference Learning Representations (ICLR), 2020.
Cihang Xie, Yuxin Wu, Laurens der Maaten, Alan L Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. In Conference on Computer Vision and Pattern Recognition (CVPR), pp. 501-509, 2019.
Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, and Hongxia Yang. Knas: green neural architecture search. In International Conference on Machine Learning (ICML),
Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. Network and Distributed Systems Security Symposium, 2018.
Greg Yang and Edward Hu. Feature learning in infinite-width neural networks. In International Conference on Machine Learning (ICML.,, 2021.
Peng Ye, Baopu Li, Yikang Li, Tao Chen, Jiayuan Fan, and Wanli Ouyang. b-darts: Beta-decay regularization for differentiable architecture search. In Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench- 101: Towards reproducible neural architecture search. In International Conference on Machine Learning (ICML), 2019.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In International Conference on Learning Representations (ICLR), 2020.
Arber Zela, Julien Niklas Siems, Lucas Zimmer, Jovita Lukasik, Margret Keuper, and Frank Hutter. Surrogate nas benchmarks: Going beyond the limited search spaces of tabular nas benchmarks. In International Conference on Learning Representations (ICLR), 2022.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning (ICML), 2019.
14

---

Published as a conference paper at ICLR 2024
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. Invaancess in neural information processing systems (NeurIPS), 2020.
Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. Generalization properties of NAS under activation and skip connection search. In Advances in neural information processing systems (NeurIPS), 2022a.
Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization). In Advances in neural information processing systems (NeurIPS), 2022b.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference Learning Representations (ICLR), 2017.
Barret Zoph. Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
15

---

Published as a conference paper at ICLR 2024
CONTENTS OF THE APPENDIX
The Appendix is organized as follows:
In Appendix A
we summarize the symbols and notation used in this paper.
A comprehensive overview of related literatures can be found in Appendix B.1 A detailed clarifica-
tion of the distinctions between work and prior research is present in Appendix B.2
In Appendix
we include the proof for the generalization bound of FCNNs. C
The proof for the lower bound on the minimum eigenvalue of the NTK is present in Appendix D
The extension of theoretical results to CNN can found at Appendix
Further details on the experiment are developed Appendix(F
Limitations and societal impact of this work are discussed in Appendix AppendixGGandd Appendix H tively.
respec-
A SYMBOLS AND NOTATION
Vectors/matticees/eesssss are symbolized by lovercasduuperras/ccllligpahph boldface letters, e.g., w. W, W. We use ||-||F and Il-112 to represent the Frobenius norm and the spectral norm a matrix, respectively. The Euclidean norm of a vector is symbolized by I1-1|2- The superscript with brackets is used to represent a particular element of a vector/matrix/tensonn e.g., w)()) (8) the i-th element of w. The superscript with brackets symbolizes the variables at different training step, e.g., W(1 Regarding the subscript, denote by Wi the learnable weights at I-th layer, æ; the i-th input data. [Z] is defined as shorthand of [1, for any positive integer L. We denote by X' C Rd and y C R the input space and the output space, respectively. The training data (w:; is drawn from probability measure D on X' x y. For an input a E X, we symbolize its p-neighborhood by
B(x,p) == E x||2 -
nxx.
For any W E W, we define its r-neighborhood as follows:
We summarize the core symbols and notation in Table 3
B COMPLETE RELATED WORK AND OUR CONTRIBUTION
B.1 COMPLETE RELATED WORK
Adversarial example and defense. Since the seminal work (Szegedy et al. 2013) illustrated that neural networks are vulnerable to inputs with small perturbations, several approaches have emerged to defend against such attacks, c.g., adversarial training (Goodfellow et al. 2015 | et al. | (2018). feature denoising (Xu et al. 2018, Xie et al., 2019). modifying network architecture (Xiao al. 2020), regularizing Lipschitz constant (Cisse et al. 2017) or input gradient (Ross & Doshi Velez 2018) Adversarial training is one of the most effective defense mechanisms that minimizes the empirical training loss based on the adversarial data, which is obtained by solving a maximum problem. Goodfellow et al. (2015) use Fast Gradient Sign Method (FGSM), one-step method, to generate the adversarial data. However, FGSM relies on the linearization of loss around data points and the resulting model is still vulnerable other more sophisticated adversaries. Multi-step methods are subsequently proposed to further improve the robustness, e.g., multi-step FGSM (Kurakin et al.) (018)). multi-step PGD (Madry et al. 2018). Other methods of generating adversarial examples include L-BFGS Szegedy et al. 2013 C&W attack (Carlini & Wagner 2017
NAS and benchmarks. Over the years, significant strides have been made towards develop- ing NAS algorithms, which have been explored from various angles, e.g., differentiable search with
weight-sharing (Liu al., 2019 Zela et al. 2020 al. (022), reinforcement learning (Baker et al.
2017 Zoph & Le 2011 et al. 2018). evolutionary algorithm (Suganuma et al. 2017 Real et al.
2017 2019), NTK-hased methods (Chen et al. 2021 Xu et al. 2021 Mok al.
2022 Zhu et al.
16

---

Published as a conference paper at ICLR 2024
Table Core symbols and notations used in this paper.
Symbol
Dimension(s)
Definition
Gaussian distribution with mcan and variance o
L.
Shorthand of (1.
O, o. 52 and
Standard Bachmann-Landan order notation
@ W
Euclidean norms of vector w
Spectral norms of matrix W
W
Frobenius norms of matrix W
Amin
W. Xmax
Minimum and maximum eigenvalues of matrix W Minimum and Maximum singular values of matrix W
Omin
W)
w
i-th element of vector
W
((-))-th element of matrix W
Wid
matrix W time step
N
Number of training data points
Dimension (channel) of the input in FCNN (CNN)
m
Width (Channel) intermediate layers in FCNN (CNN)
P
Pixel of the input in CNN
Filter size in CNN
Rd
The i-th data point The i-th target Input data distribution Target data distribution
1/4
IR
Dx
Dy
Element- wise activation function at (-th layer in FCNN
W1. Wi, wL
Rmxd gmxm, R
Learuable weights in FCNN, / 2- Collection of all learnable weights in FCNN (WW
W
(1 WL)
D
Rmxm
Diagonal matrix, D = Diagla (W. fi 1)), for le [Z-1 in FCNN
2022a). Most recent work on NAS for robust architecture belongs to the first category. Guo et al. (2020) first trains a huge network that contains every edge in the cell of the search space and then obtains specific robust architecture based on this trained network. MMok et al. (2021) propose a robust NAS method by imposing regularized term in the DARTS objective to ensure smoother loss landscape.
These algorithms are different from the "TK--ased methods, where we can select a robust architecture based on the NTK metrics without training a huge network.
Along with the evolution of NAS algorithms, the development of NAS benchmarks is also important for an efficient and fair comparison. Regarding clean accuracy, several tabular benchmarks, c.g., NAS- (Duan et al. 202I), NAS- ----B-nnh-211 (ong & Yang 2020) and NAS- Bench-301 (Zela et al., 2022), have been proposed that include the evaluation performance of architectures under standard training on image classification tasks. More recently. Jung et al. (2023) extend the scope of the benchmark towards robustness by evaluating the performance of the pre-trained architecture in NAS-Bench-201 in terms of various adversarial attacks. However, all of these benchmarks are under standard training, which motivates us to release the first NAS benchmark that contains the performance of each architecture under adversarial training.
Bench- 101 (Ying et al. 22019. TransNAS-
Neural tangent kernel. Neural tangent kernel (NTK) was first proposed by Jacot et al. (0018)
that connects the training dynamics of over- pve-pparameterized neural network, where the number of parameters is greater than the number of training data, to kernel regression. In theory, NTK provides a
tractable analysis for several phenomena in deep learning, e.g., convergence (Allen- et al. 2019).
generalization (Huang et al. 2020), and spectral bias (Cao al. 2019 Choraria et 2002). The study on the NTK has been expanded a range of neural networks including fully-connected networks (Jacot et al. 2018), convolutional networks (Bietti & Mairal 2019). and graph networks (Du et al. 2019b).
The analysis has also been extended from standard training adversarial training. In particular, Gao et al. (211) prove the convergence of FCNN with quadratic ReLU activation function, relying on the NTK theory, which suggests that the weights of the network are close to their initialization (Jacot et al. 2018). Zhang et al. (2020) provide refined analysis for FCNN with ReLU activation functions and prove that polynomial width suffices instead of exponential width. More recently, Wang et al. (2022) present convergence analysis convergence of 2-layer FCNN under certified robust training. From the generalization perspective, the guarantee of over- peee-aatmttee FCNN under standard training has been established in Cao & Gu (2019); Zhu et al. (2022a). In this work, extend the scope of generalization guarantee of over aver-parameterizer networks to multi -bjjti-o training, which covers the case of both standard training and adversarial training. Meanwhile, Huang et al. (2021) studies
17

---

Published as a conference paper at ICLR 2024
the impact of network width and depth the robustness of adversarially trained DNNs. From the theoretical side, Huang et al. (202I) is based on the Lipschitz constant for robustness evaluation while analysis builds general framework for the generalization guarantees on both clean and robust accuracy
NTK has brought insights into several practical applications. For example, in NAS, (Xu al. 2021 Shu et al. 2022 Zhu et al., (022a) show that one can use NTK as a guideline to select architectures without training. As kernel, NTK can be used in supervised learning and has demonstrated remarkable performance over neural networks on small datasets (Arora et al. 2020). Lastly, NTK has also shown its potential in virtual drug sereening. image impainting (Radhakrishnan al. 2022). and MRI reconstruction (Tancik et al. (220))
Let us now provide further intuition on why training neural networks via gradient descent can be connected to the NTK. Let us denote the loss as (WW) = - (f(xr: W) y²²)² By choosing an infinitesimally small learning rate, one has the following gradient flow: de ---((WW)) l.). By
dw
simple chain rule, we can observe that the network outputs admit the following dynamics: ar(wit)) de
-K % (f(Wiit) y), where K [+]
@a(wwl)))
@f(witt)
NRNN the NTK at f step. Hence,
aw
OW
NTK can be used to characterize the training process of neural networks.
B.2 CONTRIBUTIONS AND RELATIONSHIP TO PRIOR WORK
In this section, we clarify the contribution of our work when compared to the prior work on robust NAS. Specifically, our work makes contributions both theoretically and empirically.
From the theoretical side, our work differs from previous theoretical work (Zhu et al. Gu 2019) in the following aspects:
2022a
Cao &
Problem setting: Cao & Gu (2019) build the generalization bound of FCNN via NTK and (Zhu et al., 2022a) extend this result under the activation function search and skip connection search. Instead, our work studies the robust generalization bound of both FCNN/CNN under multi-objective adversarial training. How to handle the multi-objective clcan/robust accuracy, more general architecture search (CNN) is still unknown in prior theoretical work.
Results: Differently from Zhu et al. (2022a); Cao & Gu 2019) that are based on the sole NTK for generalization guarantees, our result demonstrates that, under adversarial training, the generalization performance (clean accuracy and robust accuracy) is affected by several NTKs. Concretely, the clean accuracy is determined by one clean NTK and robust NTK; while robust accuracy determined by robust. NTK and its "twice" perturbation version.
The technical difficulties lie in a) how to build the proof framework under oulti-objective training by the well-designed joint of NTKs and b) how to tackle the coupling relationship among several NTKs and derive the lower bound of the minimum eigenvalue of NTKs. Accordingly, our work builds the generalization loroonnguaaa guarantees of the searched architecture under multi-objective adversarial training. Our results demonstrate the effect of different search schemes, perturbation radius, and the balance parameter, which doesn't exist in previous literature.
From the application side, we release an adversarially trained benchmark on the -AS-bench201 search space, which differs from previous benchmark in the following aspects:
Motivation: As a comparison, existing benchmarks on the NAS-benchhl search space are built on standard training (Dong & Yang 2020; Jung al.) 2023). ). Since robust NAS algorithms usually include the evaluation results under adversarial training Guooetal 2020 Mok al. 202T), our bench- mark facilitates a direct retrieval of these results for reliable reproducibility and efficient assessment.
Statistical result: In Table I we present the rank correlation among different accuracies within our proposed benchmark as well as the benchmark in (Jung et al. 2023). The observation underscores the significance of adversarial training within our benchmark. Specifically, it suggests that employing Jung et al. (2023) identify resilient architecture may not guarantee its robustness under the context of adversarial training. Additionally, in Figure [] we can see a notable difference between these two benchmarks in terms of top architectures id and selected nodes.
18

---

Published as a conference paper at ICLR 2024
Lastly, investigate the correlation between various NTK metries and the robust aceuracy of the architecture in the benchmark. By integrating this result with our theoretical generalization bound, we can inspire practitioners to craft more robust and potent algorithms.
C PROOF OF THE GENERALIZATION OF RESIDUAL FCNN
C.I SOME AUXILIARY LEMMAS
Lemma (Corollary 5.35 in Vershynin 2012 Given matrix W =R x where each element is sampled independently from (0,1),, for every Ç 0, with probability at least 1-2epp(-S (2/ /2) one has:
/m1 /m SS minn (W> S muxe (W) S //mmm + /
where max (W) and min (W) represents the maximum singular value and the minimum singular value of W, respectively.
Lemma 2 (Upper bound of spectral norms of initial weight). Given weight matrix W E EIRT x where m, 2 m2 and each element is sampled independently NO 1.), then with probability at least 1 2exxp(-m//2) one has:
W 11 33
Proofoff Lemmal Following Lemmal
1 w.p. at least -exp( /2), one has:
12
mi + m2 +))
mi
Setting Ç /m and using the fact that m, 2 m2 completes the proof.
Lemma (The order of the network output at initialization). Fix any I [1,L- and æ, when width satisfies m = (6) with probubility at least - 2-eexlleelmmmm - over the randomness of (w(") Fi= we have:
Cimin S |
SCmax:
where Otmax and Ctuax are some (1) constant.
Proof. The result can be obtained by simply applying Lemma the initial weights and Lemma C.I Du et al. 2019a).
The following lemma shows that the perturbation of a: can be considered equivalent perturbation of the weights.
4.mma Given any fixed input E X, with probability at least - 1-e mm2 over random initialization,
for any & E X satisfying || (zz-áll 2 S and any W E <B(WiL, .T), there exists W E (L, P) such that:
-( 15156-1,
((l,,W)Di((z..))) 151L--1,
((t,))
Proof. Let us define:
W1 x)x a 2
W. Wi+
Obviously, W, satisfies w W Ø. Then setting W 2.... W, equal to W2,..., W, will make the
output of the following layers equal. Besides, by Lemma with probability 1- - 2e [1] <3 and thus
2--m// mm/2
one has
19

---

Published as a conference paper at ICLR 2024
W1( x x)
Wi ( x 1|>||||
W1 Wi
WW Will2/e 11ll@==aall
|
| 1
< w/
11 +T)
p s pT
which indicates that
W W-W W
x3p+ + pr w.p. Lastly, by triangle inequality, with probability
1 1-2e mm/ we have:
Will <
W W + W Wil)
<T+3p+Tp,
which completes the proof.
The following lemma shows that the network output does not change too much if the weights close to that in initialization.
Lemma 5. For W E B(W("),)) with v 3, if the width satisfies m = Q(N/6), with probability at least 1 2(L 2(L-1))xx))) ()xxp()xx))) (-m/2) -, one has:
| -f- Se (Cr.ppCCppp Crmax)T.
Proof. To simplify the notation, in the following proof, the variable with is related to W, and without T related to W For the output of the first layer, have:
5 - 11g = (
SCrip W,
Wi |101| St112p
For the /-th layer ( (2,3,..,.L-11,,, we have:
ft
(Wi (Wif----) ( -ai
1 7 W (W
01 (W
+ F 5-1
(By triangle inequality)
CLip
<
W Wifi-i 1i-1-WWfi- + f-11 fi
(By the Lipsehitz continuity of a))
L
Crap
Wi(fi-1-f--1) 1 W W.) ||
+ Fi - fi ||
L
CLip
[IWille| [ f
||
+
W, w/
Ji |,}
Ji-1 - fi s1-1 1
T.
2
CLip
(Will++1) 1 11)
f|-
+
CLip
[| -
si-1 -
+1[fi-1ll2)
T.
T.
CLip
(1 (IWillg (IWill++))+1) +T)+++++++
Fi
fi - || + CLip - |||s| 1|
L
20

---

Published as a conference paper at ICLR 2024
Therefore, by the inequality recursively and Lemmas 2 and with probability at least 1 2(L
1 1)exp( (00mmmmm2))) - 6, we have:
F2-1-1 fL-1
Ciip (3 (3+ +1 11-2--1-1
CLip -Imax I
+
(By Lemmas 2 and
T.
Lip (3+T)
+1]
fi 11
Σ
1.-3
CLiP + TC TCimax
CLIP
(By recursion)
L
6CLip +1
4-2
1-3 Σ
6CLip +1]'
CLip TCimxx
Lipp+
L
L
k=0
60Lip +1
L-2
1
(6CLip/ DBCCippL++100 1) CLip TCmmax
LCpipt
L
1-60Lip/L L-1 L
5000L (CLip -Cmaxx(
Lemma 6. For W (&W(lll with I when the width satisftes mn -==/2N/0/ and p PS with probability least 122exxp(mm22) has:
-W)
6CL (1+ +Cmmax)
W.WW-W. w
18c 60LD
(2-3) (2-
+ -tmax)
Proof. To simplify the notation, in the following proof, the variable with is related to W. and without is related to W. The variable with related to input A, W), and without related to input æ. For instance, denote by:
fi fi)
D; - Diag(ar ( (Wiffi1)),
f: f W),
D = Diag(o (Wifi-1),,
fi
D Diag( / (Wiffi-)))
Then, let us prove the first inequality. We have:
f- (1
w)
(ii.fo-1) (WLrI--1) -
Σ E( (11-BVV.F--V/////M--
1-1
(wi.fi---fin + (fr. 1: -LL)
Σ
(l=3) wi)
1=1
(7)
(1--)))--
< <|1iTl|2 Fo-1 F2-1-fue 1--1-foa fL-1
+
fL-1 - f f2-1
110 |00 -L
(1 3) v w. f.i wi)
Σ (V.....W.
+
The first term can be bounded by Lemmas 2 and 5 as follows:
| 1
fi-1-1
fi-1-ff-11
w
[1]
+ T0ة w
11]
(1) F1 +
1 - sL-11l
-
2
< (3+r)26 6Cim (Ciip + TTmax)t.
21

---

Published as a conference paper at ICLR 2024
The second term can be bounded by Lemmas 3 5 with ك 1 as follows:
B 1 - 82-1 | -wwll2
<B (1 1i-i--1-111= fT.-1
+ 5 - 1 11) (1 -
-w0"
WT. - /00/"
+
2
3 336 0Lip (CLip + Chmax) (2T (3p+3
(8)
The third term can be bounded by Lemmas 2 and 3 as follows:
(1-3)
Σ
V W: W.J. W. W.ii
1-1
-1-33
M
W
II (D, mmm (WW:
r=1+1
(9)
<1-33
Iwulle II r=1+1
(D W Wi
fl
L-1
CLiP (3+7)+1)4-17
(1--3)
Σ
CLip (3+T)
(11-3)Ctunse e COLIT.
Similarly, the fourth term can be upper bounded by e Plugging back Eq. yields:
Si (C + 6Cru (C ( (2T+3 + +fmax 6Crip
<18 (.tp))(Cip++tmmaaa
which completes the proof of the first inequality in the lemma. Next, we prove the second inequality in the lemma following the same method.
(11
WWW -
fi... 1 -un.
(( (1-BVVw.F-NV../WWWWW
1=1
-
Wi..Fr- - f(-1) (f-- - wL
Σ (1 wi)
-8 (10)
< <| 7o-1- f2-1 +(1 +(1-))))))))))) 3) fL-1 f || - wwellz
1-1
(1- (W: w/
WV. (p..
(3 6C (CLip +Cmas ) (1
CLii (CLip + Ctmaax (27 + -Cmaxe 6CLip
< 186 6Liv (2 (C -ipppppppp Cimax]T
Lemma 7. There exists an absolute constant C such that, for any e and any W W EB(W with r < C1c(B ()c(0+1)- (CLip + Cfuaa) - e 6CUpp with probability at least 1 when the width satisfies ==s((N/)) and p < 1, one has:
- -6,
AL L(x, W 2 C(A, CKA.H///HNNNNN/////DNN/AAAAAAAAA
W)
22

---

Published as a conference paper at ICLR 2024
Proof. Firstly, will prove the first inequality. Recall that the cross-entropy loss is written as ((2)=log(11)) (oo[][=[p) and we denote by ([) Then one has:
-
2elyfl.y-00 v-(f-f) (By convexity of f(=)).
2((ys] V. (1--3)1,, - (0 w) 11
-(L-5WWW(CCW//WWWWAAAAAAA). w -Ki (By chain rule),
where we define:
(1- " -lvsllv (DF...
=
Thus, it suffices to show that K1 can be upper bounded by
C'vs-
(,,, W- W ( ww)
11
00 (Cmm)
V ++2
-
L-1
S 100 (Ctp))C 22
wi)
$186 (1+ + Cfmax 2,30 601up 44 +430mmax7
224(1+B)e 60up (Ciáp +Cmaxx
SG
(11)
where the first and the third incquality is by triangle inequality, the second inequality is by Lemma and the fact that (f W) yl 11,, the fourth inequality follows the same proof as in Eqs.
and (9). and the last inequality is by the condition that if = (2) (CLipp +tmaa)) e
-60L
for some absolute constant C2.
Now we will prove the second inequality of the lemma.
-elvf--
(' (By convexity of ((z)).
W) 2e(ufl- (1- - ( -W -R2
=(1-3))
w) w)-ng
(By chain rule),
where we define:
Clyft li k2: -o:=f//l -f-- ( -Aw-w-Ww-A-
Cwyf W
Thus, it suffices to show that 12 can be upper bounded by e. Following by the same method Eq. with Lemma 6 we have:
11
< 186 6CLD (2- (Cii CCmax + 2,30 60Lip +430mmm24
< (2(3-3)e2 6Ch (Crip Cfmax SSE,
where the last inequality is by the condition that if < -3)) + -1e 660t.p for
some absolute constant Cj. Lastly, setting C = max Cz and noting that (3 (8- < (1+ completes the proof.
23

---

Published as a conference paper at ICLR 2024
Lemma 8. For any R, 0 such that 222 (0,1)) there exists:
m (ot.olyyRRLLLCippp.. (0
such that if m 2 m then for any W E B(W BB. Rm-1/2), under the following choice of step-size CipPCras Rmaze 12C /(2=2v) for some small enough
y= veppCrip Ct mm [2Cuu]] and N L,2 R2
absolute constant the cumulative loss can be upper bounded with probability at least 1 1 by:
(a,, w/
1
1 N
(ax
W W +3c,
N
N (AA (1,
C(Ap( (2 W1))
-le 6Cup where C1 is small enough absolute constant so that the requirements on r in Lemmas and 7 can be satisfied. Let Rm fmm-1/22 1/22// then we obtain the condition for W E B WW 17..i.....
Proof. We set Cie(1 B) (Crip Ctmax)
12 CT 2 + 3)² (mmax) 2e We now show that Will ,..., WIN] are inside B ((W .7) well. The proof follows by induction. Clearly, we have WIl E BBW ,r). Suppose that W ...., [(W(l) ,r), then with probability least 1 1-6', 8", we have:
W
w w P
Σ 2 (1- 31 v w. C(x W
1=1
$> 1) Vw, Cw,,(,,
+ V C(Ap wrb)),
T--1
CLie ( Wi -
SYNCLi w l2
II
r=++1
CLip (3+7)+1)
(3+
L
L6nNCLLip
Plugging in our parameter choice for and N leads to:
w f w || S 331ip Ctmax GCuup LR-E -1mm ST,
where the last inequality holds as long as m 2 3Cp.p Cmaa 12 LR-CT-1 Therefore by induction we see that will "y.., wiNI E B(W ,). Now, we are ready to prove the first inequality in the lemma. We provide an upper bound for the cumulative loss follows:
C(x, w (il,, -(
< V L(x, W
18) ) VV w (.)
w
+e
(By Lemmal 7
(wil-- [++
w W
+c
γ
WW
w 11 1
Wil
w
W
W 113 +c
27
| w
+e
27
W |
W
62 C2 Cinax e 12Crip
+6.
2
27
24

---

Published as a conference paper at ICLR 2024
Telescoping over i I.....,V, obtain:
1
((,,,W(l))
N
N W - +18, Pnnxx 120 DE
Ca,,, W
2
N
LR
Cla,, [(x,, W
1 Ci Cimax 22C +E
2ym
Σ [(x, +33
where in the first inequality we simply remove the term -1 W [[N+1] / to obtain an upper bound, the second inequality follows by the assumption that W E B Rm R12), the third inequality is by the parameter choice o and N. Lastly, we denote 8= 2-e=pe-eppm + (0,1). which requires m 2 (1(1) satisfied by taking m =() One can follow the same procedure to prove the second inequality in the lemma that is based on Lemma 7
C.2 PROOF OF THEOREM 1
Proof. Since W is uniformly sampled from [Will, .., W.Nj,, by Hoeffding's inequality, with probability at least 1-
[1 (2,, <0 <0]++/ +V 21og(1/8"))
E (Co ())
(12)
N
Since the cross-entropy loss {(z) = log + (exp(=x]] satisfies 11=50} < 4l(2), we have:
yi f(x;) w (8) <0 < 4C(xx,,W11)
(13)
with (() W 1)) Next, setting e = LRv OLip 6Crpp / 2 in Lemma
leads step-size 7 = //RR ( LC C Iimax OC then by combining with Eqs. (12
and (13), with probability at least 1 - 8 8", we have:
12 LR.
2log glog(1/8")
Ew (C (W))) -
(C(x,, w
(14)
V2v VN
N
for all W B(W 11/2).
Define the linearized network around initialization W as
Fwu w (m) == (x. B)V ( Sw (A) W+ -Wl)).
(15)
We now compare the loss induced by the original network with its linearized network:
((x;,W")-+e -(())- ((y:-)-(www w (z:)) = E(v f(),, -(()) -wui, w (xx))
(æ;)) - SChp
) Rm 1/2 5 L-NN--1
where the first inequality is by the 1-Lipschitz continuity of E, the second inequality is by Lemma 6
with Rm 1/2 < 3, i.c., m 2 R2 /9, the third inequality holds when m 2 122cnp (1+ (CLip
Ctnax) N 2, Plugging the inequality above back to Eq. (14). we obtain:
N
12
LR
21og(1 1 1o") (16)
W (L) S
Ely: Fw w- (w...w-(x;))) +(
/2v
VN
N
Next, we will upper bound the RHS of the inequality above. For cross-entropy loss we have: {(2)
N for >> B :==log /og(l//exp(//V// 122 1]} (log.N). We define:
= max ((; N
(B+
25

---

Published as a conference paper at ICLR 2024
Then for any i [N], we have:
ys 1u(l -y:
-BB=BBB
As result, we have:
Eyy (
Denote by 11-= B.J, where
J=m 1/2 (vee:///.vc////////// fww Vww.://wwww.""""...oooo//v//o//r
J ==m= 11/2. [veceVeecwWWwwee.voo " (rr (A) wll,,, wi(
Let PAQ T be the singular value decomposition of Jall. where P
+m Q
RNXN ,AERRXX Let us define Wyer PA- y', then we have:
Jal wec QAP PA PA- Q y'=y''
which implies ((1 (1-))3J +BJJT Wvvec = yy Moreover, we have:
| === PA -P-''' 1/ =y QA Q y u (JalJan)) =y" [[J ((Ja[Jaa)) - (K.n) +y" (Kal)) "'y
(17)
<N(B+B)) { (K..) 12 (B+ (Kan)"
By Lemma 3.8 in Cao & Gu (019) and standard matrix perturbation bound, there exists
m² (6, L, N, Amiu (Jan), such that, if m 2 m" then with probability at least - 6, Jal is positive-definite and
K all
[I Jan all 125
Therefore, Eq. 17) can be further upper bounded by: || 113 - O0y k-ly). y). Eq. 16). with probability least 1-8 -8-8" 8", we obtain:
Plugging it back
N
12
Ll ll
log(1/8")
Ew (CB (W))
(BB) +(
+1)
+1
22
VN
N
Liy K N
Kn'y y
10g(1/8")
N
which finishes the proof for generalization guarantees on clean accuracy.
In the next, we present the proof for generalization guarantees on robust accuracy. The proof technique the same as that of clean accuracy.
Since W is uniformly sampled from (Wil),... ..., ...,WAl)), by Hoeffding's inequality, with probability least 1 8";
E (C 1
1
N
ye- (i wil), w <0] +
2log(1/8")
(18)
N
N
1=1
Since the cross-entropy loss {(z) = log + -expeepp-00 (-)p satisfies
we have:
px (AA, w (1), w (1) <0 < 4C(AA w wl)).
(19)
Next, setting = LR CRP/ Ciip Cimaxe 60rpp / 2 in Lemma 8 leads to step-size ? =
(vR/(/2Ci.n))) tipp 5Crip 50ri N), then by combining with Eqs. 18 and 19 with probabil-
ity at least 1 1 8"" we have:
12 LR
2log(1/8")
w (robustt (W))
(C(A, (IA,
22 VN
(20)
N N
4
12 LR
2log(1/8")
/2v
VN
N
26

---

Published as a conference paper at ICLR 2024
for all W ((W))),,m RR Rm²///), where the second inequality is by the definition of the worst-case adversary (-)))
Next, compare the loss induced by the original network with its linearized network defined in Eq. (5)
W'),
(A7 (
= S( ("")) E(ve FWIn, w. (2;
SaA W W - (A5 W (I))
S 186 (1+ (C Cmmax) Rmm 1/2 +6p+ 2Pm -1/2p)
S LRR-1/22
where the first inequality is by the I-LLiscchitz continuity of é, the second inequality is by Lemmas with Rm Rm211/2 - 6 2Rmm 1/2 <3, i... (R(++1p)) 3(1 -2)], the last inequality holds
when m 2 0C (1 + (C + Cimax R( + p) (LR/N 18c 60 (1 () + )fmax))=
Plugging the inequality above back to Eq. 20 obtain:
N
12 V2v
LR
Mlg(1188")
Ew Crobuust (W)) S
Mys Fww. (4
+1)
VN
N
(21)
Lastly, noticing that based on Eq. 15):
Fwillw w- (4,,,,,ll)))
= =((A)(a, ((1-)) (") 3V/ (w.,, (. w.
Then can define the Jacobian
Jan Jan
where
1/2, "
w.l1)) will W ) (A) wlll), , w(l))))
-a-=m 1 (vo
Lastly, by replacing Jau by Jal as in the step on clean generalization bound, we can finish the proof.
D THE LOWER BOUND OF THE MINIMUM EIGENVALUE OF ROBUST NTK
We have shown that the minimum eigenvalue of robust NTK significantly affects both clean and robust generalizations. Hence we provide a lower bound estimation for its minimum eigenvalue.
Assumption 3. We assume the perturbation << d)) For any data (x p² <1, in other words.
C -
(Z,,I, $1 d
where C is some constant independent of the number of data points N and the dimensional of the input feature d.
Remark: For example, we can set -:= 2C Here the o(1/d) means a high-order small term of 1/d and can be omitted. This assumption holds for large d in practice, e.g., d= 796 for MNIST dataset and d -d=33000 3072 for CIFAR10/100 10/10 dataset.
Theorem 2. Under Assumption and we have the following lower bound estimation for the minimum eigenvalue of K
- (1- +2p
Amii 2ur)))=0
where (l(a) is Herriit coefficient of the activation at the first layer.
27

---

Published as a conference paper at ICLR 2024
Proof.
Amin K2)) 2 Amin
2m Σ
us (o))) _u(01)P(=1((877))
Nguyen Mondelli 2020 Lemma D.3)
(01 M0 xx)
Iakiing -log (1 (te, .2,ي -
2
min | 1 - (N |E[N]
1)maxl (0.,22)1))
(Gershgorin circle theorem)
2214(0112
(- ( >1 ( AH
i*)
2211(01)3
( ix
E PROOF OF THE GENERALIZZATON OF RESIDUAL CNN
In this section, we provide proof for residual CNN. Firstly, we reformulate the network in Appendix E. Secondly, we introduce several lemmas in Appendix E.2 in order to show the upper bound for the cumulative loss (Lemmal The remaining step the same as FCNN.
E. REFORMULATION OF THE NETWORK
Firstly, we will rewrite the definition of CNN in Eq. 2 in way to facilitate the proof. Specifically, we define an operator Φ1 (-) that divides its input into p patches. The dimension each patch is kd. For example, when the size of filter h = 3, we have:
(1.0:2))
(x(1--11--1)) T
Φ (1()= =
E
Rddxp
(x (1.02))
(x (x(4+-1pt)))
Similarly, we define Φi Fi) E Rxmxp for the subsequent layers. Then we can re-write the formula of CNN as follows:
F = 01 (W1d
F L
(Wio((
2515
F2 (Wt,FF.. Fi-1),
(
where learnable weights are Wi E <ldixkd Wie RmxXm p 2-.,..,,L and W,, E Rmxx,
E.2 SOME AUXILIARY LEMMAS
Lemma (Upper bound of spectral norms of initial weight). With probability least the norm of the weight of residual CNN has
2exp(-m/2). 222l22)22LL--- 2-2-2(())ees) (100:mmmm22_LLL-22epp-m-ms/m///
the following upper bound:
w 11 53
||w]] || $3
Proof. The bound of W 2, for [L- can be obtained by directly applying Lemma
Regarding
[ [1] le. note that w [1]
E Rm xx, then we bound its norm by Lemma 2 as follows
L
11 (1.))
53/D.
28

---

Published as a conference paper at ICLR 2024
with probability at least 1 1- 2pexp(-mpp mm
Lemma 10 (The order of the network output initialization). Fix a and X, when the width satisfies m m= N/6), with probability at least 1 11--22xx((mm//a -ô over the randomness of (w!")) 2 Ji=1 we have:
Cimin S F((,,wl)>| &Cmaxx
where Ofmax and Ommx are some (1) constant.
Proof. The result can be obtained by simply applying Lemma 2 the initial weights and Lemma D.1 in Du et (019a)).
L
Lemma 11.
For W (B(W)), with 33, when the width satisfies m= m=--(22///000 and p 1, with
probability at least 1 - -1- 1exp(( (exxppxxm/22 kmm2)m))))))))))))) - 6, one has:
Fr. -F (X,,
Proof. To simplify the notation, in the following proof, the variable with is related to W, and without Ts related W For the output of the first layer, we have:
F
F F
01
Φ1 (x) 01 ( WitWWWWss (x)) SCip
W1 Wi 11 (X))
SCLip
W1
F. Wi
VKl X STVRCipp
For the (-th layer (1E we have:
F
F
oi (Fid(( (Wich(FF-)) F1-1
L
Widh (Wid) (F)-)) [ ((VO-)-))))
L 0/ W
+aj-1
F-1 F1
(By Triangle inequality)
CLiP
Widh Fr W (F
+
F 1 Fi
(By the Lipschitz continuity of at)
CLip
|| 12 (F(-1)) 22 F7
+
W Wi - -W:
12 1
F1-1 F
CLip
vR{ Wiill
F - Fz
|1
+
W -W
Fi-1
+
F F1-1-FU Fi
2
F
CLiP b
Vkl W Will
1||
CLip
Therefore, by applying the inequality recursively and Lemmas and 1 (((-1))xppp mm/2) we have:
10 with probability at least
F F7-1-FF-11
CLip vT(3+T)+ 2 Fi.-2
CLip ViT Ctmax VieTCimxx
(By Lemmas Saaimassannnd and 10
L
CLiP (x(3+T)+1]4-- F Fj
L-3
CLip VK(3+T)+11
CLip
<1
ViT L
(By recursion)
L
F
L
1=0
Ctip 1 L COCCuV/(//RLaaa Ctnax)+.
L-3
Ctap
Crap VKTCumux
<(6
Σ
6
1k+1)*
L
L
1=
29

---

Published as a conference paper at ICLR 2024
Lemma 12. For W W.W & with T 3. when the width sattisfies m== and p 1,
with at least 1- 2pg
we have:
=18 60 (1+.3) (1+33 CCmaa)
(ww.://www...aaa........//////.- $18/pe Lap
5 (2 (2-3)) Cimos)
Proof. To simplify the notation, the following proof, the variable with is related to W, and without is related to W. Then, let prove the first inequality.
f (1 (L-3) WW w.)
W (i..ii-i) (win.11.1)) (11-))))111 111-3
-
(1-B3
(22)
< <|
- fL-1 -
+.3
ft. f2-1 | -WLll2
L-1
(1 - 3) v W.. wi)
Σ
(W.
+
1=1
The first term can be bounded by Lemmas 2 and 11 as follows:
||07,.12 1| F T-- Sr.-1
$ (
un) [1]
w 11]
(.)
51-111 + 1--1-11111
1|2" + ii
< / 7 72c 60
(VECLip Ctmax) )T.
The second term can be bounded by Lemmas 3 4
and with ps follows:
f1.-1-fu-1 f2-1 100 1001--1111 -w
<3 (1| =1 - (1 11 J/L 1 (1wo - -w0²" +
(1)
s <Be VLL
(23)
The third term can be bounded by Lemmas 2 and 10as as follows:
V W. WW, -w:)
(1-3)
Σ
1=1
L-1
CLip vs Ww wi
<(1-3) 3)
CLipl (
II
(24)
r=1+1
Crap (1(3+7)+1))-11
<1- 3)
Σ
(3pp(3//))))
(1-3)
30

---

Published as a conference paper at ICLR 2024
Similarly, the fourth term can be upper bounded by hypppmaxx e Plugging back Eq. (2) yields:
- -f ((1-)W/W--WWWW---WWWW
1 (3/D+T)2e ( (VRCrip+ Ctmax) Be @vnocu (VRCtip
+ /Vpp @VrCUPT
I 18 avaCrup (1+3)(VKC1.)) Crmax)T:
which completes the proof of the first inequality in the lemma. The second inequality can be proved by the same method as in Lemma
Lemma 13. There exists an absolute constant C1 such that,for any c <> and any W.W E (((W]"),) 1-11 with T S Cie(v/CLip + Cimax) -imax))1p-122 1-011/2--0upp vR, with probability at least 1 2exp(-exppccl - -m/2)- -
2(L- ([L=))epp-Kkm/9) (2tpp)/)))2xxpmmp/p/1p - one has:
f(x, C(x.)) (or + (11 (ww.://wwww................aaA.a
W
- W) -W
Proof. Firstly, we will prove the first inequality. Recall that the cross-entropy loss is written as ((2) ((z)=log) log(11 +exp((====)) and we denote by L(x, W) Ely- f(x, W)). Then one has:
-(a,
- {lyf]
2elwsl-w saoullww-F-aa (F-)) (By convexity of ((2)).
2Clufl-v v W (w) -w) )
-K1
(By chain rule),
where define:
= (f- (1-3)///-- - (BV..--..
Thus, it suffices to show that can be upper bounded by e
Cvu (10
W h (1--
W.
-
/De @ VTOOND (L++))((ECtiit+tnnnnna T
V Vw Fwi.w-w
1 (1000ii01+111111 (1+3) COmex) 2
Σ [(v.. w:) +281 - w
1-1
118/DEVVRCLI (1 (1+ +3) BNCLL (sCLip - Ctuax) se,
- Ctmax)) - 2,3 2. @VECLiP +430mmax
(25)
where the first and the third inequality is by triangle inequality, the second inequality is by Lemmal
12
and the fact that 16" [fr W)) S 1,, the fourth inequality follows the same proof as Eqs. 23
and (24p. and the last inequality is by the condition that if 7 S C2c(1 + (.-5)-11 10-'p-11 11/1pp_11(___ (
/K( k
Lip
Ctiaxx:) e GG-rprp for some absolute constant C2. Following the same method in Lemma 7 we
can prove the second inequality if S C3e -1p -11 (VRC1.p +Cmmxx) ) - -6-RR/C for some
absolute constant Cz. Lastly, setting C₁ = max C22 C2} and noting that (3 8) < 3)+
completes the proof.
31

---

Published as a conference paper at ICLR 2024
Lemma 14. For any E,8,R> O. there exists: m =O(ooly(R,LL Lipp.,3))) 22 Algg log(1/6) such that if m 2 m², then for any W BB(Wlll Rm RR Rm-1/2), under the following choice of step-size
Y ve/ rre/(CaappCCtme mL ma 122 and iterations N L R2 Cap fimxx e 12 /(2:2 for some small enough absolute constant the cumulative loss can be upper bounded with probability at least 8-8 by:
N C( D. W
1 N Σ
)s
N
N N
(
(2; (1
C
1=1
Proof. We set - -(CnC Clmax) P 1/2e 6CLivV where C1 is small enough absolute constant so that the requirements on T in Lemmas 12 and 13 can be satisfied.
We Cel Crmax) e --rrpp where Ci is small enough absolute constant so that the requirements on in Lemmas and can be satisfied. Let Rm 1/2 < r, then we obtain the Rm-1//2 3) p(CCCip + Cimax) 2e 120Lip vxx We
condition for W E B(WL!!, -), i.e., m 2 R C now show that W WiN] are inside ((W [1] [T) as well. The proof follows by induction. Clearly, we have w E B( W/ 1] .T). Suppose that W/1 w B(W ,T), then with probability at least 1 1- 8', we have:
W 1+1|
w w
Σ> (1 (1-33) V C(a, W. (ib). w/61]
j=1
Sx(1 (3113)/ V ((a,,
+>BN V Vw, C(A, M W()) (
SYNCrhp W
II r=1+1
CLie
I
V 112 +1) W, W Wi
CLap [k(3+)++11 L
1-1-1
SxNCCip(3/Pt+)) VKCtmux
I6,N V ByRCup.
Plugging in our parameter choice for and N leads to: || w "
tee by RRRO -im ST,
where the last inequality holds as long as m 2 30Lip e 12 LIRC Therefore by induction we see that Wil ..... WIN| E (WW(L) Now, we are ready to prove the first inequality in the lemma. We provide upper bound for the cumulative loss as follows:
L( W (t) -(a,,
(1- C( W ) W C(4 W( wll).
wil - w +e
(By Lemmal
(wlil_ [++1] w W
+e
7
WWM w ++1
1
Wl
w
W
W 12
+E W 11 C WWW ( w(
27
WW
w -
+e
27
|
W
W
-
62 PrC Prnas 12/nCLiPP
+c.
2
27
32

---

Published as a conference paper at ICLR 2024
Telescoping over i I, we obtain:
N
IWa) W
(ax W
+ +18 118 Pnp. fmax e 12VTCCUP
2Ny
N
LR
C(x;,W")
+ 18 Dn maxx 12 12 +6
2ymN
Clx,, W +3e,
where in the first inequality simply remove the term -1| WI[++] W (2)) to obtain an upper bound, the second inequality follows by the assumption that W* E B(Wl), Rm 1/2), the third inequality is by the paraneter choice of ry and N. One can follow the same procedure to prove the second inequality in the lemma that is based Lemma 13
ADDITIONAL EXPERIMENTS
F.1 CORRELATION BETWEEN FGSM-NTK AND PGD-NTK SCORES AND ACCURACY
We present comprehensive analysis of the correlation between NTK scores and accuracy in Figure The following 10 NTKs are selected: clean NTK, robust NTK with O (3/25 (3/255,8 8/2558/ subjected to FGSM/PGD attack, the corresponding robust twice NTK subjected FGSM/PGD attack. The result demonstrates that robust NTK has higher correlation compared with standard NTK under adversarial training. Moreover, our analysis indicates a general trend wherein NTKs with FGSM attacks display higher correlation with accuracy than those subjected to PGD attacks. These results suggest that employing NTKs with FGSM attacks is preferable for guiding robust architecture searches.
0.527
0.533
0.540
0.537
0.549
0.531
0.536
0.534
0.556
rooR, 3233
0.546
0.552
0.559
0.556
0.568
0.550
0.555
0.553
0.575
Accuracy PGD, No33
0.543
0.550
0.556
0.553
0.565
0.548
0.552
0.550
0.572
FOOM 8255
0.601
0.608
0.614
0.611
0.622
0.606
0.610
0.608
0.628
PID, 8235
0.598
0.604
0.610
0.608
0.619
0.602
0.607
0.605
0.625
KNAS
P00
PCD 8/255 NTK
nooM 31255
FGGM 8255
FoSM 3/255
pasi 8/255
3/255
8/255
3255
Figure 6: Spearman coefficient between NTK-score, and various metrics. The label with subscript in the x-axis indicates the score w.r.t the robust NTK while the one with subscript p indicates the score w.r.t the twice robust NTK.
33

---

Published as a conference paper at ICLR 2024
F.2 EVALUATION RESULTS ON NAS APPROACHES
In Table 7. we provide additional evaluation results on NAS approaches, e.g., Adv Rush (Mok et al. 202T). KNAS et al. 2021). EigenNAS (Zhu et 2022a), NASI al. 2022). NASWOT (Mel lor et al. 2021). For KNAS, we use the data with PGD attack to construct the kernel. We follow the same set-up in Xu et al. (02T) to efficiently compute the NTK. Specifically, we randomly select 50 samples and estimate the minimum eigenvalue of NTK by its Frobenius norm. Similarly, in EigenNAS, we choose the trace of the NTK as proposed in Zhu et al. (202aa). Regarding NASI, NASWOT, and AdvRush, we use the official open-source implementation produce the result. For DARTS, we use the first-order implementation, i.e., DARTS-VI, VI, from the library of Dong & Yang (020))
F.3 GRADIENT OBFUSCATION SPARSE AND DENSE ARCHITECTURES
Originally pointed out by Athalye et al. 2018), 8), gradient obfuscation is a cause for the overestimated robustness of several adversarial defense mechanisms, e.g., parametric noise injection defense (He et al. 2019) and ensemble defenses (Gao et al. 2022). Such gradient obfuscation might exist in the defense several dense or sparse architectures (Kundu et al.) 202T). In this work, we employ vanilla adversarial training as defense approach, which does not sufter from gradient obfuscation, as originally demonstrated in (Athalye et al, (2018). Given the huge considered search space with 6466 architectures, we investigate whether the sparsity of the architecture design might have impact on gradient obfuscation. Specifically, based on the search space in Figure [ we group all architectures in terms of the number of operators "Zeroize", which can represent the sparsity of the network. Next, we select the one with the highest robust accuracy in each group and check whether this optimal architecture satisfies the characteristics of mon-gradient obfuscation in Table
Table 4: Characteristics of non-gradien obfuscation Athalye et al. 20118
One-step attack performs worse than iterative attacks.
b) Black-box -bx attacks perform worse than white-box attacks.
c) Unbounded attacks fail to obtain 100% attack success rate.
d) Inereasing the perturbation radius p does increase the attack success rate.
c) Adversurial examples can not found by random sampling if gradicnt- bbsed attacks do not.
Table presensss the evaluation result of these architectures under FGSM, Square Attack, and PGD attack with varying radius. We can see that all of these architectures clearly satisfy a), c), d). Regarding e), all of the networks still satisfy it because gradient- based attacks find adversarial examples. For b), only the sparse network with 4 "Zeroize" does not satisfy. Therefore, we can see that these architectures can be considered without suffering gradient obfuscation, which consistent with the original conclusion for adversarial training in (Athalye et al. 2018).
Table 5: Testing of gradient obfuscation for architectures with different sparsity.
Number "Zeroize"
FGSM (3/255)
Square (3/255)
PGD (3/255)
PGD (8/255)
PGD (16/255)
PGD (32/255)
PGD (64/255)
PGD
PGD
Clean
(128/255)
(255/255)
0
0.7946
0.6975
0.6929
0.6924
0.4826
0.1774
0.0083
0,0000
0.0000
0,0000
1
0.7928
0.6933
0.6884
0.6874
0.4798
0,1744
0.0077
0.0000
0.0000
0.0000
2
0.7842
0.6832
0.6786
0.6779
0.4711
0.1739
0.0080
0.0000
0.0000
0.0000
0.7456
0.6515
0.6482
0.6472
0.4442
0.1599
0.0079
0.0000
0,0000
0.0000
4
0.5320
0.4560
0.4427
0.4528
0.3191
0.1393
0.0193
0.0010
0.0000
0.0000
F.4 ROBUSTNESS TOWARDS DISTRIBUTION SHIFT
To make the benchmark more comprehensive in a realistic setting, we evaluate each architecture in the search space under distribution shift, We choose CIFAR-10-C (Hendrycks & Dietterich 2019).
34

---

Published as a conference paper at ICLR 2024
80
60
Accuraty
50
Accuraci
50
30
30
20
10
stel potte)
masier, Mark
show
pirelees3
gassionn Relbe
0
detoran Barz
brighnesst
fogt
atort Mord
frond
0
glaca Stor)
impoite nelsel
cmptrnst
Beg comprosiion
nlsstic tratsfomm
70
60
Accuracy
Accuracy
50
40-
60
30
20-
20
thot mmans
noten Slard
snows
dletatos
geussan rotess
deficst biog
brgg
figh
zoan 8ies
frods
glans Mar
impuis roteds
contratt
lsep comprension?
etastic ransforss
Figure 7: Boxplots for accuracy under various corruptions and severity levels (1 and 5) of all 6466 architectures in the considered search space. Red line indicates the accuracy of random guess.
Table Spearman coefficient between various accuracies on CIFAR- 10-C and adversarial robust accuracy CIFAR-10. We that the ad veresariaal robust accuracy has relatively high correlation with all corruptions except for contrast corruptions.
PGD 3/255
FGSM 3/255
PGD 8/255
FGSM 8/255
Shot noise
0.984
0.984
0.965
0.968
Motion blur
0.990
0.990
0.980
0.982
Snow
0.995
0.995
0.989
0,990
Pixelate
0.996
0.996
0.984
0.988
Gaussian noise
0.981
0.981
0.961
0.965
Defocus blur
0.993
0.993
0.983
0.986
Brightness
0.993
0.993
0.984
0.986
Fog
0.916
0.916
0.918
0.918
Zoom blur
0.992
0.992
0.978
0.982
Frost
0.991
0,991
0.985
0.987
Glass blur
0.993
0,993
0.981
0.984
Impulse noise
0,947
0.947
0.936
0.938
Contrast
-0.555
-0.555
-0.574
-0.571
Jpeg compression
0.996
0.997
0.984
0.987
Elastic transform
0.995
0.995
0.984
0.987
which includes 15 visual corruptions with 5 different severity levels, resulting 75 new metrics. In Figure we show the boxplots of the accuracy. All architectures are robust towards corruption with lower severity levels. When increasing the severity levels to five, the models are no longer robust to fog and contrast architectures. Similar to robust accuracy under FGSM and PGD attacks, we can see a non-negligible gap between the performance of different architectures, which motivates robust architecture design. Moreover, in 6 we plot the Spearman coefficient between various accuracies under corruptions with severity level 5 on CIFAR-10- 10-C and adversarial robust accuracy on CIFAR- 10. Interestingly,
that the adversarial robust accuracy has relatively high correlation with all corruptions except for contrast corruptions. As result, performing NAS on the adversarially trained architectures in the benchmark obtain robust guarantee of distribution shift.
35

---

Published as a conference paper at ICLR 2024
Table 7: Result of different NAS algorithms on our NAs-Robbcchhh2
FGSM (3/255)
PGD (3/255)
FGSM (8/255)
PGD
Method
Clean
(8/255)
Optimal
0.794
0.698
0.692
0.537
0.482
Regularized Evolution
0.791
0.693
0.688
0.530
0,476
Clean
Random Search
0.779
0.682
0.676
0.520
0.470
Local Search
0.796
0.697
0.692
0.533
0.478
Regularized Evolution
0.790
0.693
0.688
0.532
0.478
FGSM (8/255)
Random Search
0.774
0.679
0.674
0.521
0.471
Local Search
0.794
0.695
0.689
0.535
0.481
Regularized Evolution
0.789
0.692
0.686
0.478
PGD (8/255)
Random Search
0.771
0.676
0.671
0.520
0.471
Local Search
0.794
0.695
0.689
0.535
0,481
KNAS 0.767
0.675
0.67
0,521
0,472
EigenNAS
0.766
0.674
0.668
0.52
0.471
Train-frec
NASI
0.666
0.571
0.567
0.410
0.379
NASWOT
0.766
0.674
0.668
0.52
0.471
AdvRush
0.587
0.492
0.489
0.352
0.330
Differentiable search
DARTS
0.332
0.286
0.285
0.215
0.213
Architectures ID
30.8
Average rbust acuuray
1414
15452
30.6
10733
30.4
7632
1062
13082
302
14624
Edga41
Edg042
Edga43
Edgea4
Edgoas
Edgo46
Zumino
Sti
Canv
Zeroloe
Sti
3x3 Danv
Zerobo
Skip
3x3 Conv
Zeroboe
3x3 Conv
Zamio
Conv
3x3 Dan
Zeroioe
Camv
3x3 comv
Ave
1x1
1x1
1xt
Figure The operators of each edge in the top-10 (average robust accuracy of PGD-3/255, PGD-8/255 FGSM-3/255 FGSM-8/255) architecture in Jung et al. (2033). We can see notable difference from the one present Figure in terms of architectures id and selected nodes. Additionally, the best architecture in NAS Rob-eRRbbBncc---- 201 has higher accuracy (= 60%) than that of the best architecture (ze 30%) in Jung et al. 2023).
G LIMITATIONS
Our benchmark and theoretical results have a primary limitation, as they currently pertain exclusively Fully Connected Neural Networks (FCNN) and Convolutional Neural Networks (CNN), with no exploration of their applicability to state-of oftto---tthtteee the-art art vision Transformers. Furthermore, our study is constrained by search space encompassing only 6466 architectures, leaving room for future research to consider more expansive design space.
Our analysis framework could be adapted for a vision Transformer but the analysis for Transformer is still difficult because of different training procedures and more complicated architectures. The optimization guarantees of Transformer under realistic setting (e.g., scaling, architecture framework) in theory is still an open question. Secondly, similar to the -TK-based analysis in the community, study the neural network in the linear regime, which can not fully explain the success of practical neural networks (Allen-Zhu et al. 2019 Yang & Hu 2021). 1.. However, NAS can still benefit from the NTK result. For example, the empirical -aK-based NAS algorithm allows for feature learning by taking extra metrics (Mok et al. 2022). Additionally, though our theoretical result uses the NTK tool under
36

---

Published as a conference paper at ICLR 2024
the lazy training regime (Chizat et al. 2019), NAS can still benefit from the NTK result. For example. the empirical NTK-based NAS algorithm allows for feature learning by taking extra metrics, see Mok et al. 2022 for details.
H SOCIETAL IMPACT
Firstly, this work releases NNSS benchmark that includes the evaluation result of 6466 architectures under adversarial training, which facilitates researchers to efficiently and fairly evaluate various NAS algorithms. Secondly, this work provides the generalization guarantee for searching robust architecture for the NAS community, which paves the way for practitioners to develop train-free NAS algorithms. Hence, we do expect any negative societal bias from this perspective. However, we encourage the community to explore further the general societal bias from machine learning models into real-world applications.
37


Reviews:
[{"review_id": "zPRViYFFWX", "reviewer": "Reviewer_QErk", "summary": "This paper presents two primary contributions. Firstly, the authors have developed a search space encompassing over 6,000 adversarially trained architectures, addressing the limitation of prior studies that lacked such a comprehensive search space. Secondly, the authors demonstrate that robust architectures can indeed be identified within this search space by employing robust NTK.", "questions": "1. Could you please clarify what 'optimal' refers to in Table 2?\n2. In the first column of Table 2, what is the definition of 'criterion' used for?\n3. It would be interesting to learn about the correlation results when measured with the existing clean NTK, such as in previous works by Zhu et al. and Cao et al. (which could correspond to beta being 0).\n4. Referring to Figure 3, it appears that there is a high correlation between clean and robust accuracy. However, I am curious about the implications of using just clean NTK values for adversarial robust search and how that might affect the interpretation of the results.\n\n\nMinor Comments\n1. In Table 2, the entries in the first column are not center-aligned. This misalignment could be corrected for improved readability and a more professional presentation of the data.\n2. The interpretations of Figure 3, specifically parts (b) and (c), pose some difficulties. Enhanced specificity in the explanations accompanying these figures would greatly facilitate understanding.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper's principal strength lies in its creation of an adversarially trained search space, which required 107k GPU hours to construct. This significant advancement is poised to benefit researchers focusing on robust architecture search in the future immensely.\n2. The analyses conducted within this adversarial search space are considered to be novel. It is particularly noteworthy to observe cross-sectional evidence in the NAS search space, confirming the expectation that a 3x3 kernel size CNN layer contributes to robustness. Additionally, the findings concerning the correlation between clean accuracy and robustness in the face of adversarial attacks are intriguing.\n3. The paper is well-written, offering clarity and ease of comprehension.", "weaknesses": "1. The paper lacks a detailed explanation and justification for the necessity of employing twice perturbation, as mentioned at the end of page 7. It remains unclear why robust NTK requires a double perturbation when conventional adversarial training typically examines generalization from a single perturbation.\n2. While it is posited that robust accuracy is influenced by the adversarial term, the theoretical analysis provided appears to be a reiteration of what was presented by Zhu et al. and Cao et al. in the context of clean NTK. Consequently, the contribution in this area seems minimal. Notably, the robust term A*(x,W), which is contingent on W and x, was not accounted for in the theoretical framework and was instead treated as an independent input variable. This oversight could impact the applicability of the theoretical analysis.\n3. The paper employs an evaluation metric that is not standard, raising questions about its normalization. The last part of page 4, in the dataset paragraph, should clarify whether the metric is normalized before the attack and then inputted into the model. Additionally, it would be beneficial if the authors specified whether the same perturbation radius (32x32) used for ImageNet was applied during training.\n\n* All of the previous concerns have been resolved through the rebuttal. Thanks for the clear and explicit response to my initial concerns and questions. Therefore, I have revised my score to 6. Regarding normalization in evaluation, I would like the author to double-check whether normalization is also applied inside the attack functions, specifically after adding the perturbation and before forwarding it to the model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ShknvefTI5", "reviewer": "Reviewer_dbFp", "summary": "The paper first presents an adversarially trained benchmark based on NASBench 201, and present NASRobBench 201.", "questions": "1. Apart from the doubts in weakness, I have the following question:\n\na. How you add noise \"twice\"?\n\nb. Please extend the NTK score vs accuracy correlation with more recent and stronger attack scenarios.\n\n\n### Post rebuttal:\n-------------------------\n\nThanks authors for rebuttal.\n\nDespite the limited novelty of the work, which the work did not commit anyway, I believe the work is good enough with enough empirical evaluations. Thus, I increase the score to 6! Though a 7 might have been the right score for this. I refrained from giving it a 8, just due to limited novelty scope, however, I think this work could be a useful add to the adversarial network benchmarking community.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "There is not much literature that presents a unified robust NAS benchmark, in that sense the work targets a unique space of research that needs exploration.\n\nThe NTK score vs accuracy correlation sounds interesting.", "weaknesses": "1. It has been well known that adversarial robustness often may occur due to gradient obfuscation and is applicable for different sparse and dense model architectures [1,2]. Thus, a discussion on that would be necessary. In specific, is there a way to benchmark based on a subnet's susceptibility to be more prone towards obfuscation?\n\n2. Di you use ImageNet or ImageNet-16-120? As the Fig. 2 and the contribution section has mention of each.\n\n3. Please demonstrate the efficacy of the NASRobBench on Autoattack.\n\n4. The related work of Adversarial example generation is not up to date, the author should discuss more about the auto attacks and other contemporary attacks.\n\n[1] Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples, ICML 2018.\n\n[2] DNR: A Tunable Robust Pruning Framework Through Dynamic Network Rewiring of DNNs, ASP-DAC 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XGj9oOJEmH", "reviewer": "Reviewer_AZRS", "summary": "For fast and standardized evaluation of Neural Architecture Search algorithms, it is important to develop various benchmarks that contain a large set of architectures and their quality measured with diverse performance metrics. In this vein, the paper builds and releases a new NAS benchmark that considers not only the standard accuracy of evaluated architectures but also their robustness against adversarial attacks. The authors extend the existing NAS-Bench-201 benchmark by adversarially training the NAS-Bench-201 architectures and evaluating them on clean and perturbed data. The proposed robust NAS benchmark is named NAS-RobBench-201. Additionally, the authors theoretically characterize the robust generalization performance of architectures using the Neural Tangent Kernel (NTK) framework.", "questions": "Please refer to the weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- As the authors note, adversarially training takes considerably more time than standard training with the cross-entropy loss. Given the enormous computational cost of adversarial training and evaluating a large number of architectures, I believe the authors really have done an impressive set of experiments.\n- I generally agree with the necessity to create a NAS benchmark that targets robustness and generalization beyond standard test data.\n- I do not feel confident enough to review and comment on the more theoretical parts of the paper. The proofs were not reviewed thoroughly, and thus I cannot vouch for its correctness. I am, however, familiar with the NTK theory, and I find the idea of extending the NTK-based analysis to explain adversarial robustness interesting.", "weaknesses": "- Currently, the robust accuracy is measured only under FGSM and PGD attacks. I think the performance under stronger attack methods (e.g., AutoAttack) is necessary to make the benchmark more reliable.\n- The authors observe that the standard and robust accuracies exhibit a meaningful level of correlation. If they are, do we really need a separate robustness benchmark that includes robust accuracies? Wouldn’t searching for the optimal architecture in a conventional sense work as a good proxy and naturally result in a more robust architecture?\n- I believe that NAS-Bench-201 is too constrained of a search space to accurately reflect the vastness of the potential architecture pool. For instance, [1] shows that many NTK-based methods fail outside the boundary of NAS-Bench-201. While this is a good first step towards building a more comprehensive robustness benchmark, it would be great if the authors could show that the experimental and theoretical analyses hold outside the tested search space.\n- It would be nice to include the performance of trained architectures on out-of-distribution data and/or datasets with distribution shift in the benchmark. Incorporating these other types of robustness would make the benchmark more comprehensive, especially considering that in real deployment scenarios, the architectures will encounter generic OOD data more often than adversarially-perturbed data.\n- In section 4.4, the authors study the correlation between the minimum eigenvalue of the NTK matrix and robust accuracy. I understand that this NTK-score is derived from theoretical resultss, but have the authors studied the relationship between other NTK-based scores (e.g., condition number [2]) and robust accuracy?\n\n[1] Mok, Jisoo, et al. \"Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training?.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.\n[2] Chen, Wuyang, Xinyu Gong, and Zhangyang Wang. \"Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective.\" International Conference on Learning Representations. 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)