The NTK Adversary: An Approach to Adversarial Attacks without any Model Access
Authors: Nikolaos Tsilivis
Julia Kempe
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial Attack
Neural Tangent Kernel
Adversarial Examples

Abstract: Adversarial attacks carefully perturb natural inputs, so that a machine learning algorithm produces erroneous decisions on them. Most successful attacks on neural networks exploit gradient information of the model (either directly or by estimating it through querying the model). Harnessing recent advances in Deep Learning theory, we propose a radically different attack that eliminates that need. In particular, in the regime where the Neural Tangent Kernel theory holds, we derive a simple, but powerful strategy for attacking models, which in contrast to prior work, does not require any access to the model under attack, or any trained replica of it for that matter. Instead, we leverage the explicit description afforded by the NTK to maximally perturb the output of the model, using solely information about the model structure and the training data. We experimentally verify the efficacy of our approach, first on models that lie close to the theoretical assumptions (large width, proper initialization, etc.) and, further, on more practical scenarios, with those assumptions relaxed. In addition,  we show that our perturbations exhibit strong transferability between models.

Under review as a conference paper at ICLR 2022
THE NTK ADVERSARY: AN APPROACH TO ADVER- SARIAL ATTACKS WITHOUT ANY MODEL ACCESS
Anonymous authors Paper under double-blind review
ABSTRACT
We initiate the study of direct generation of adversarial examples for trained neu- ral networks via the analytical tools afforded by Neural Tangent Kernel (NTK) theory. In particular, these advances in Deep Learning theory allow us to de- rive expressions for optimal adversarial perturbations, together with the output of the model on them. This leads to simple, but powerful strategy for attacking models, which, crucially, does not require any access to the model under attack, training of a substitute model. Instead, we solely exploit information that is available prior to initialization, namely model structure and training data. We ex- perimentally verify the efficacy of our approach, first models that lie close the theoretical assumptions (large width, proper initialization, etc.) and, further, more practical scenarios, with those assumptions relaxed. In addition, that our perturbations exhibit strong transfcrability between models. We provide evidence that, in several cases, there is close match between our methods and the strongest- dott adversarial attack, projected gradient ascent, in terms of efficacy and transferability.
show
INTRODUCTION
Adversarial examples, term coined by Szegedy et al. (2014), are inputs of a machine learning model that are carefully crafted so that the model is mistaken on them. Their existence, together with the empirically verified susceptibility of many classifiers them (Szegedy al.) 2014] Carlini & Wagner, 2017), imply an important security headache for modern machine learning. The ultimate pursuit for robust and immune models calls for an extensive understanding of the different versions of adversarial examples that model may encounter. In most cases, an adversarial perturbation (an instance of small non random noise) is added to training or test data to form an adversarial example. This procedure is called an adversarial attack.
There has been a large body of work on designing such attacks. The most successful attacks exploit model information through its gradient with respect to the input. By perturbing the data in directions of the largest change in loss function, they are able to drop the performance of naive classifiers to almost zero (Goodfellow et al. 2015. Moosavi-Deztooli et al. 2016), Carlini & Wagner [017] Kurakin et al.) 2017] Madry et al. 2018). While successful, these gradient-derivel attacks require access the parameters of the trained modch-which might be unrealistic for practical applications. To relax this requirement, so called black-box attacks only query the model. Observation of the model outputs allows estimate the aforementioned gradients either by training substitute models Papernot et al., 2016 2017: Liu et al.) 2017) or by diiteediffeeence methods (Chen et al. 2017 llyas et al. 2018). Nonetheless, to some extent even these strategies require access to the model.
Our contribution: In this work, we leverage recent advances in the theoretical understanding of trained neural networks to devise adversarial data perturbations that, surprisingly, require neither access to the model nor training of a substitute model, and do not use any model information what- soever, apart from the model architecture. We thus reveal an interesting phenomenon: the suscepti- bility of trained neural networks to adversarial examples does not depend on their specific weights; instead these blind spots may be calculated a-priori, prior to initialization, even before the train- ing starts. Although this is already known to extent from prior work that trains substitute models, we demonstrate that this notion holds from first principles that only require the a-priori description of the model. Our powerful, highly agnostic attack is derived from Neural Tangent Ker-

---

Under review as a conference paper at ICLR 2022
nel theory (Jacot al. 2018 Lee al. 2019 Arora al.] 2019b), which allows to describe the dynamics of the muddient-descene based training procedure of a neural net as kernel regression, with architecture- and data-dependee deeeedentt (but parameter-agnostie kemel (NTK). At high-level of abstraction, our approach exploits the NTK description of the function the model has learned at the end of training, and proceeds to maximally perturb this function. To illustrate more precisely, let (x, v) E IR x {-1,+1 + be an input sample, E IR a small perturbation, and f IRd + R denote the model after training has converged. Then, as we show, in the NTK regime:
f(x 7) R f(x) + n
for some z E Rd that depends on the training data and the NTK kernel only. Although the above derived for regression models, we show that this simple expression naturally leads to a family
of adversarial attacks on classifiers, depending on the choice of constraints imposed on 77. We also cover the general case of multiclass classifiers, which is similar spirit to Eq. (T). As our experiments on MNIST and CIFAR suggest, we are able to confuse classifiers with rate that in some cases approaches current benchmarks that require model access.
In summary, in this work we initiate the study of "NTK-derived" adversarial perturbations and make the following contributions:
1. We derive expressions for the output of a converged model on adversarial inputs, based on the theory of the Neural Tangent Kernel (Sec. 3
2. We propose a family of simple attacks that exploit the aforementioned description. These attacks either depend on analytical expressions afforded by the NTK or on finite approx- imations of the true quantities (" ("empirical" NTK), obtained by initialized replicas of the attacked models (Sec. 3
3. We experimentally verify the efficacy of our approaches layer model that operates in the NTK regime (Arora et al., (019a) (Sec. 4.J and show that favorably compares to the strongest benchmark (PGD attack), without any access to model weights.
simple wide single hidden
4. Further, we demonstrate that our attack works practical settings: fully connected and convolutional, undefended, networks, trained in standard ways (cross entropy minimiza- tion, stochastic gradient descent, default initialization, etc) are quite susceptible to NTK noise. We show this both in the case where the noise is generated from the NTK of the model itself, even though the assumptions of NTK theory do not necessarily hold (Sec..4.2) well as for transfer attacks with adversarial perturbations generated by models within the NTK regime (Sec.
BACKGROUND AND RELATED WORK
Our work bridges two as yet disparate areas: generation of adversarial examples for trained neural networks at inference time and the description of the dynamics of neural network training in the infinite width limit, with the Neural Tangent Kernel.
Adversarial Examples. Let f be a classifier, x be an input (c.g. a natural image) and its true label (c.g. the image class). Then, given that f is an accurate classifier on x, we define x to be an adversarial example (Szegedy et al. 2014) for if the following two hold:
1. d(x, x) is small for some distance function d. Common choices in computer vision appli- cations are the Ep norms.
2. f(x # y. That is, the perturbed input is being misclassified.
There are many approaches on how to generate such examples and they are often classified into two large areas: white- box and black-box attacky White-box attacks assume perfect knowledge of the
While we focus on la attacks in this work, we remark that the introduced framework is much more general and the adoption of other similarity measures is equivalent optimizing Eq. [I] (a linear objective) with the desired constraint on 17.
"Wille we use the word "attack" multiple times, it must be emphasized that the existence of adversarial examples and the search for robust models are not security-only concerns. They align very well with concepts, such interpretability and human-like perception (Tsipras al. 2019 [lyas 2019).
2

---

Under review as a conference paper at ICLR 2022
model under-attack and they mainly rely on optimization procedures to maximize the "confusion" of the model (Szegedy et al. 2014 Goodfellow et al., 20155] Moosavi-Dezfooli et al.) 2016 Kurakin et al., 2017: Carlini & Wagner
Madry et al., 2018). The most widely adopted method is
called Projected Gradient Descent (Kurakin et al., 2017] Madry et al. 2018) and performs multiple
gradient steps on the input space to discover adversarial examples. Formally, if [(f(xx,)) y) denotes a loss function, then, in the context of loo adversaries, setting x" = the update formula for PGD is:
x Ixx4 (x' + (gg(Vv.L(f(xx))
t= O.....,,NN N
(2)
where IT (-)) projects the input inside the allowed fo ball, and a is gradient step- hyperparam- eter. xN is the final adversarial example. Such attacks are the most powerful to date. Black-box attacks, on the other hand, are not allowed to estimate the aforementioned gradient directly, but rather are restricted to querying the model without accessing the parameters. A lot of these attacks proceed by collecting pairs of inputs and predictions from the model, then train another classifier f on them, attack / with white-box attacks and finally use those generated adversarial samples to attack f (Papernot et al. 2016 2017 Liu et al., 2017). The empirical success of such strategies relies on the phenomenon of transferability of adversarial examples (Szegedy et al. 2014 Papernot iet al., [016;] Tramer et al. 2017: Liu et al.) 2017): it has been observed that adversarial inputs de- signed for successfully fooling one classifier, manage to also fool others. A related line of research abandons the need for creating substitute models, at the cost of allowing multiple curated queries to the model infer the loss function (Chen et al., 2017 Hyas et al., 2018). Finally, hard-label black box attacks have been considered in the literature, in which an attacker observes only the prediction of f (Brendel et al. 2018 Cheng et al. 2019). The adversarial attack we propose does not fall into any of these categories, since it does not query the target model at all. More related to the scope of this work is the so-called "no-box" setting (Chen et al. 2017: Bose et al.] 2020 Li et al., 2020), where an adversary is prohibited from querying the model under-attack. However, to the best of our knowledge, practical attacks under this threat model do train substitute neural networks, making them incomparable to work.
Neural Tangent Kernel (NTK). NTK theory plays an increasing role in the quest to theoreti- cally understand deep learning and the elusive concepts of optimization and generalization in over- parametrized networks. It connects deep learning to Gaussian Procesxes and kernels. The seminal work of Neal (1996) considered the infinite width limit of neural networks with one hidden layer and showed that at initialization the network is a function drawn from a Gaussian Process with an associ- ated kernel that depends on the activation function. Recently, this limit (and non asymptotic versions of it) has been revisited either for deep random networks where only the last layer is being trained
(Lee et al. (2018); de G. Matthews et al. (2018); Novak et al. (2019)) or fully trained networks with gradient descent (Jacot et al. [0188] Lee et al. 2019 Arora et al. 2019b). In the latter case, Jacot jet al. (2018) identified a particular quantity that governs the dynamics of the training procedure of neural network with randomly initialized parameters @ computing an output f(x; 0) Fd + R, which they called Neural Tangent Kernel.
The NTK is defined as the expectation of the inner product between the gradients of the function with respect to the random initialization of its parameters 0 evaluated on all inputs x,, Xj, i.e.,
hxx,, x,) = E, (x;; 2 V))
(3)
While first studied in fully connected networks, it is possible to define neural tangent kernels for any sane architecture (Yang (020)).
In the infinite width limi (and under appropriate initialization), the training dynamics of the net- work with infinitesimal learning rate can be described by a differential equation with a constant NTK. Moreover, crucially, in the case of squared loss this gives rise to closed-form description of the training dynamics with the NTK. For ease of presentation we restrict to the case where the expected network output at initialization is zero; then the expected output of the network at conver- gence of training becomes (Lee et al. 2018)):
(4) where X' E Baxd is a collection of n d-dimensional training data, X E TRn' xd is a test set and H : Reixd x Ro2xd R xna is the NTK (for fixed input datasets, H is matrix). For some
fo (x() = (((,,)
for non asymptotic statements see Arora al. 2019h).
3

---

Under review as a conference paper at ICLR 2022
models, this kernel can be computed in closed form analytically by computing the expectation the initializations. It can also be approximated by an empirical kernel via averaging over a few initialized instances (Jacot et al. 2018 Lee et al. 2019).
Finally, there has also been work on the intersection of the two areas, though with very distinct emphasis ours. Recent work (Bubeck et al. (2021): Bartlett et al. (221)) studies the existence of adversarial examples in overparametrized random neural networks, exploiting some local linearity of the functions computed by such networks. The only prior work that leverages NTK theory to derive perturbations (published almost concurrently with the preparation of our work) is due to
Yuan & Wu 202I). yet with different focus and without our modification to the standard approach to the optimization problem, that generates the perturbations (see at the end of Sec. (3. That work concerned with what coined as generalization attacks: the process of altering the training data distribution to prevent models to generalise on clean data. In contrast, our work analyses trained models to analytically derive their weakness to adversarial perturbations at inference time. Besides that, our work introduces analytical expressions for the perturbed data and the output of the network on them, something that does not follow from the methods Yuan & Wu (202I) (even if extended to the problem consider).
ADVERSARIAL PERTURBATIONS ON WIDE NEURAL NETWORKS
Here we present the main methods introduced in this work, assuming the asymptotic conditions on the parameters required for Eq. hold, and showcasing its implications for adversarially perturbed imputs.
3.1 SCALAR OUTPUT
First, we treat the simpler case of networks with scalar output, which allows us to illustrate the various scenarios examine. We assume the training dataset consists of n d-dimensional samples, X' E Faxd, with labels y E +1],
Suppose we would like evaluate a model described by Eq. on slightly perturbed variations of the original training data. Then, slightly abusing notation, set, X +e, that is x;+-7); for all x; E X' for small, but unknown, perturbations n)- By Taylor expanding around x; and neglecting second order terms in the perturbation nh we can write the ij-th element of H(X, X') as follows:
h h(x, = h(x; + m. Mx) z 1(x, x,) x))+ + V h(x,
(5)
For each row H., (,, X) we obtain:
ERixn
V Vx, x1) V 7x,h(x, XT2
H. (X, = (X,
7h.
(6)
AjeRaxd
Hence, H(², X) can be written as H(X, for a perturbation matrix A, with i-th row A,,
ni A7 Substituting into Eq. we get:
= ( + ()) A
Thus, the output of the model on x; is:
f(x,) 9: A 11
(8)
y: + गh A H X)-
leading to the linear expression advertised in Eq. (I. The adversarial perturbation n, changes the output by ni." z; = n. A, ('',')))))) X an expression which allows us to compute the adversarial perturbation maximally change the output within the desired constraints ni- We call such
4

---

Under review as a conference paper at ICLR 2022
adversarial perturbations derived from Eq. 8 NTK-perturbations. Notice that here we essentially compute a first-order approximation of the function of the model on perturbed data.
Regression versus classification Eq. 4 gives exact description for regression models with LSE (Lz-loss), while adversarial examples typically are studied for classification models. As is stan- dard, we view such regression models as classifiers by thresholding the predictions (i.e. taking the sign of the output in the case of binary {-1. classification tasks) or by outputting the maximum prediction (in the case of multiclass problems).
Inspecting Eq. (8), maximal "confusion" of the classification model is achieved by aligning 7 with -yz (directed towards the decision boundary). In case of the commonly used foo restriction, i.e. [|m bloe I e. the optimal adversarial perturbation is given by:
n = -y sgn A H (H,
We remark that the above derivation allows us to exactly compute an optimal adversarial attack for very wide models trained with gradient descent under certain asymptotic conditions necessary for Eq. 4 without any knowledge of its weights. The computation requires an expression for the NTK and its gradient with respect to the training data. For models where analytical expression of the NTK is available, only access to the labeled training data is necessary (see Sec. 4.1). In more complicated models or those that deviate from the assumptions for Eq. one can compute an empirical kemne by sampling over kernels at initialization over a few instances and obtain the matrices A; with autodifferentiation tools.
Adversarial perturbations of unseen (test) data Eq. 8 has been derived for perturbations of the training data. Consider now the case when we evaluate Eq. on perturbations of unseen test data, that is on X + c. Then, Eq. 7 becomes:
A) f(²) + X)
(10)
Again, soiely the second term depends on the perturbation, so we proceed by choosing a maximally perturbing direction as before. The only difference lies in the matrix A that now depends on the test set X (see App. A.I.I). In practice, an adversary can calculate the NTK H(X, X²) offline (even a small batch of it, as the experiments suggest) and calculate the optimal perturbation on new test input x, by computing the corresponding row of the matrix A. We will use pTrtterturbattons derived in this fashion by default when perturbing test data, unless otherwise stated.
No access to training data cases when the adversary has no access training data (inputs and labels), they can make the assumption that the test data comes from the same distribution, which implies that the model would have learned a similar mapping had been "trained" on test data instead. They then can directly compute the perturbations via the techniques above, provided they have access to the test set labels (this also holds for multiclass classifiers of Sec. (.2)). We will refer to this method as -agnosiic test method.
Absence of labels We note that all our methods require access to training (or test) labels, but want to stress that they work even in the setting where the adversary has access to either labels. To evaluate Eq. (4) and derived expressions, the adversary can "estimate" the labels by observing the output of the attacked model and substituting it instead of the required label vector V Such oracular access to the trained model is in contrast to the main point of our work and we don't examine this method in our experiments, but want to point out its existence.
3.2 MULTIPLE OUTPUTS
We adapt the derivations of Sec. 3.1 to the setting where the output dimension is larger than one in the underlying regression setting, leading to multiclass classifier. The derivations can be found in App. A. and lead to the multi-dimennional analogue of the linear Eq. (1 for f(x) E R y E IR:
n Z1
11
f(x: + +m) = 4
(11)
5

---

Under review as a conference paper at ICLR 2022
Again, the z E Rd can be computed from the NTK and its derivative well the training data labels. Exactly analogous considerations as in the binary case allow to adapt this expression to perturbations of the test data, or to substitute access to labeled test data instead of training data.
At this point we have choice of how to adversarially perturb the classifier to achieve the largest effect on the network output. We present the two most obvious methods, with details in App. A.1.2
Max-of-l1 perturbation: Similar in spirit to traditional approaches in adversarial attacks CCrllnii & Wagner (2017)) we choose 77 such as most efficiently decrease the correct response r" while maximally increasing one of the false responses + r". The solution is given by:
k max I|z, Z,- (11) r= 1,
7 = cagn
(12)
Of perturbation: For one-hot vectors y; we could, instead, maximize the cross-entropy between the labels and the new outputs, thus choosing to produce a maximally mixed output. r* is the correct label, this yields
R (z. z,-)):
7i esgn
(13)
To summarize, we have shown how the NTK based approach allows us to approximate the model output perturbed data to first order and then analytically design the optimal perturbation. Note how this contrasts with common approaches, which numerically (and often iteratively) optimize a first order approximation of the loss with respect the perturbation (PGD procedure).
4 EXPERIMENTS
In this section, present experimental evidence the efficacy of our method. First, we test the performance of NTK perturbbd data on a simple wide single-layer model, that is known to perform very close to what the theory predicts. We present results binary classification tasks extracted from MNIST and CIFAR10. We also test our multiclass attack on the full MNIST dataset and demonstrate what effect hyperparameters such as batch size, magnitude and method of attack have on the final accuracy. We further provide benchmark comparisons with PGD attacks.
Then, we shift our attention models encountered more frequently in practice. We try our method on fully connected neural networks initialized with standard techniques and trained by minimizing the cross entropy loss with stochastic gradient descent. Although we violate many of the NTK assumptions, we find that our attacks still yield strong results. Finally, we provide evidence on the transferability of our method: noise crafted from -iediddee-llayrr networks substantially fools networks commonly used in practice, such as LeNet 300- and LeNet 5. Unless stated otherwise, we set the loo -magnitud the attack e equal to 0.3 for MNIST and 8/255 for CIFAR, as is common practice. All experimental details, hyperparameters and infrastructure can be found in App. A.3.I
In order to benchmark adversarially generated noise, we compare it to random noise the same magnitude. When we refer to the random noise baseline, we mean impulse noise which with equal probability perturbs each pixel of the image by =e (clipped appropriately to remain inside the al- lowed input domain; such clipping is applied to all implemented attacks). We report the average and the standard deviation of the random baseline across different random seeds.
4.1 RANDOM COMBINATION OF FEATURES MODEL.
In the first set of experiments, we test our approach on simple gradient-trained one-hidden-layer model with an easily computed (analytical) expression for its Neural Tangent Kernel and where experimental evidence confirms that for sufficiently wide hidden layer the model closely follows theoretical predictions (Arora et al. 2019a). This model of width m computes the following function f: d
f(x) = Σ a max(w,.xx x, 0),
(14)
where a, ~ Unif((-1 (1, +1]) are frozen, and weights w, are initialized from an independent Gaus- sian distribution N' I) for appropriately chosen K. We train this model in regression fashion,

---

Under review as a conference paper at ICLR 2022
by minimizing the Eg loss, and turn it into classifier by assigning +1 to positive outputs and -1 to non-positive ones. We refer to this model as the Random Combination of Features (RCF) model.
The neural tangent kernel H E R=x= for this model is given by (Cho & Saul 2009 Arora et al.
2019a) (see App. A.2 for its gradient in order to compute the adversarial perturbation):
1 Hiy = h(x,, = (
arccos
x Xx ||
Xx;
Xj+ Vi.j E [n]]
(15)
2m
This model generalizes function with multiple outputs in the obvious way. To view the regres- sion model with fz-loss as k-way classifier, we embed the labels E [K]] as k-dimensional one-hot vectors and output the prediction with largest value. Based on NTK theory, the kernel in this multi- class case decomposes; with copy of the scalar kernel corresponding to each of the outputs.
4.1.1 BINARY CLASSIFICATION
We evaluate wide models in Eq. (44 on binary classification tasks extracted from MNIST and CIFAR. On MNIST, we train 45 different models, one for every pair of distinct digits. On CIFAR, we use data from the first two classes ("car" vs. "plane"). We train until convergence. All models on MNIST record almost perfect training and testing performance, while train/test aceuracy on CIFAR is 99.35% 90.3%. See App. A.3.1 for details and hyperparameters and App. A.3.5 for scalability.
Analytical NTK First, we calculate the optimal adversarial perturbation from the analytical expres- sion of the NTK (Eq. (15)), and its gradient with respect to the first input (Eq. (23) in App. A.2) Table ssows the performance for perturbation of the training and the unseen (test) data. The per-
turbed data are misclassified with a rate that approaches 100% on CIFAR, and 85% on MNIST. We verify that our models are robust on the random baseline of same magnitude.
Empirical NTK We now attack the same model with empirical approximation of the NTK, estimating the analytical expressions in Eqs. (15) and (23) by initializing replicas of the model under attack using Eq. (3) (with different initialization for each batch to minimize variance due to choice of the random initialization). See Table for the results. Restricted by hardware limitations. estimate the kernels using mini-batches of 256 for MNIST and 1500 for CIFAR (see App. A.3.3 for details). The results are similar to the analytical case for MNIST, but not on CIFAR; we find that absence of full data is devastating for the adversary (61% vs 0%), given the higher dimension of this dataset (see, also, App. A.3.4 for more details on the effect of batch size on the success of the attack). Note, however, that this mini-bated approach relaxes our initial assumption that the adversary has access to the whole training distribution; even minimal knowledge suffices to yield strong attacks in some cases!
Training Dataset NTK (analytical)
NTK (empirical)
Random noise
binary CIFAR
0.03
60.94
99.27 = 0.06
binary MNIST all pairs
14.74 + 16.42
21.77 + 14.29
88.43 + 15.74
Test Dataset
NTK (analytical)
NTK (empirical)
Random noise
binary CIFARIO
0.45
46.05
90.24 + 0.06
binary MNIST all pairs
15.25 + 16.63
17.81 + 16.18
88.37 15.68
Table RCF model accuracy on NTK-perturbed binary MNIST & CIFAR data. We consider attacks that use the analytical kernel, an empirical approximation and the random baseline. 'he batch size for empirical kernels is 1500 for CIFAR and 256 (500) for training (test) MNIST, while for the analytical method different classification tasks.
full-batch (the entire dataset). MNIST accuracy is averaged over the 45
NTK versus PGD To compare our results against strong benchmark, we include comparisons with PGD attacks across a range of magnitudes (details on the PGD setup can be found in App. IA..II. Recall that PGD is strictly more knowledgeable attack with access to the model parameters (see App. A.4 for a comparison of the two attacks). In Fig. (left), we compare the performance of the the binary CIFAR test data. It testifies to the strength of our NTK attack, showing that essentially matches the strongest benchmark attack (PGD) even though it is completely model-paramett agnostic.
RCF model against NTK and PGD attacks of varying Lo magnitude
7

---

Under review as a conference paper at ICLR 2022
Accuracy
Accuracy
100
random
60
40
40-
20
random
0.4
Comparison of our NTK method with PGD attack and random baseline on test data for varying foo magnitude of noise e. Left: Binary setting on CIFAR with analytical kernel. is given in multiples of 1/255. Right: Multiclass setting on MNIST with analytical kernel.
Figure 1:
4.1.2 MULTICLASS CLASSIFICATION
We now train and attack the multiclass version of the RCF model on MNIST. Train and test accuracy for this model are 97.01% % and 96.74%. See App.AA.3. 13.1ffr for details and hyperparameters. We provide results using the analytical kernel, and refer the interested reader to App. A.3.3 for results with the empirical kernel. While we implement both max-of-L1 and sum-of- perturbations as derived in Sec. 3.2 we adopt sum-of-Az given that experimental evidence suggests it performs at least as well or better than max-of-L1 (see App. A...2 for details). Full kernel experiments (batch size 60K) are presented in Table (see App. AA.344 and Fig. 2 (right) for the effect of batch size on the success of the attack). We observe that the model is fooled with a rate approaching 95% Moreover, this high success rate only degrades minimally in the case where we do not have access to the training data, but only to labeled test data (training agnostic case, with batch size 10K, see Sec.
trraining-agnottic
Training Dataset
Test Dataset NTK (train-agnostie)
NTK
Random noise
NTK
Random noise
4.95
77.92 + 0.03
3.05
8.19
77.6 0.08
Table 2: RCF multiclass attacks with MNIST, using the analytical kerel..
We have also performed the comparison to PGD attacks in the multiclass setting for noise with varying &o magnitude in Fig. (right), together with the random baseline. As previously observed on binary CIFAR, the proposed attack with the analytical kernels almost matches the performance of PGD, despite the fact that our method never queries the actual model.
4.2 FULLY CONNECTED NETWORKS
After a strong validation of our proposed method in the regime where the NTK assumptions hold, we now depart to more practical models, trained with standard techniques (stochastic gradient de- scent, standard initialization of parameters) directly classifiers (cross-entropy loss rather than & regression). To explore how our attack holds up under these relaxed assumptions, we train fam- ily of fully connected networks of varying depth and width on multiclass MNIST. To compute the model-specific NTK perturbation, we approximate the empirical kernel of Eq. (3) by resampling initial parameters and using batches of data. All details can be found in App. A.3.
We present results on training data in Table 3 Our NTK-attack is surprisingly successful, despite the fact that the models are outside the asymptotic regime where they can be shown to obey Eq. 4. not to mention that even if the dynamics was close to one described by the NTK there is now no guarantee that the NTK estimated with initialized replicas is close to the actual one. These fully converged networks are fooled to below 25% accuracy in almost all models. We observe for deeper models (depth = or 6) that with increasing width the gap to the random baseline widens, matching expectation since the model is anticipated operate closer its tangent kernel with increasing
8

---

Under review as a conference paper at ICLR 2022
width (although, mentioned, there theoretical guarantees for this experiment). We leave analytical kernel experiments for these networks (which will allow full batch sizes) for future work.
depth= =2
depth= =4
depth =
width
NTK
Random
NTK
Random
NTK
Random
100
17.91
58.35 0.14
21.91
55.87 = 0.12
33.36
52.91 + 0.09
1000
23.37
69.04 = 0.24
18.79
54.99 = 0.30
27.69
58.98 + 0.08
10000
25.55
71.71 0.14
19.78
64.58 = 0.21
22.19
60.04 + 0.23
Table 3: Accuracy of fully connected nets on NTK-perturbed (e = 0.3) multiclass MNIST training data (generated with the sum-of-Az).
4.3 TRANSFERABILITY OF NTK NOISE
Finally, we evaluate how well NTK noise derived from one model "generalizes" into fooling other, well-established models. We train LeNet 300-100, LeNet and a wide Residual network on (multiclass) MNIST with standard techniques (see App. A.3. for details), and then attack them with NoK-n generated from the analytical kernel of the RCF model of Sec. 4.1 (see App. [A.3.3] for results using the empirical kernel). To compare transferability we also test how well PGD noise coming from the trained RCF performs on those architectures, and display accuracy the random baseline to quantify robustness. Table 4 presents results on training and test data. Surprisingly, we find that adversarial examples crafted from the kernel of the simple RCF model successfully fool models not believed to be captured by NTK theory. We also observe that attacks carry transferability characteristics comparable to those of the most powerful white-box attack.
noise (train)
RCF
LeNet 300-100
LeNet 5
WideResNet
RCF
4.95
3.7
24.94
60.96
PGD
0.15
0.59
18.51
62.75
Random
77.92 + 0.03
58.48 0.11
80.29 0.09
96.04 0.09
Clean
97.01
99.96
99.82
99.78
noise (test)
RCF
LeNet 300-100
LeNet 5
WideResNet
RCF
5.05
3.74
25.65
64.5
RCF (train-agnostic)
8.19
8.63
27.44
66.38
PGD)
0.12
0.61
18.76
63.45
Random
77.6 + 0.08
59.38 + 0.17
80.52 + 0.25
95.87 + 0.15 98.29
Clean
96.74
98.02
98.62
Table 4: Transfer results MNIST (train & test) with NTK-noise generated from the analytical kernel of the RCF model with the sum-of-Az attack. We compare with PGD perturbed data pro- duced by trained RCF with cross-entropy loss and we, also, report accuracy clean data.
5 DISCUSSION
In this work, we initiate the study of adversarial examples for trained networks through the lens of Neural Tangent Kernel theory, by deriving analytical expressions for optimal perturbations, and, subsequently, proposing attacks based on them. Our experiments demonstrate the efficacy of the approach in variety of settings and yield results comparable to the most powerful "white-box" attack (PGD), without model access nor training of substitute model. All these findings suggest that the methods we introduce provide us with remarkable, almost off-the-shelf, resource of high- quality adversarial examples.
By connecting NTK and adversarial perturbations, our work demonstrates that it is possible to ar- gue analytically about properties of adversarial examples on deep neural networks. We expect these tools, together with additional insights from NTK theory, to shed some light on the puzzling trans- ferability phenomenon of adversarial examples (by studying the properties of kernels of different architectures) and to facilitate the training of robust neural networks with much less compute (by solving, for example, the robust optimization problem analytically).

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY
In keeping with conference guidelines, we have tried to ensure that our experimental results were free of any bias that would misconstrue the results. As specified in the paper, all experiments were run over multiple random seeds, on a variety of benchmarks using publicly available software and hardware. We have implemented the methods using auto-differentiation tools from Pytorch au- tograd. The code for the experiments is self contained and references appropriate instructions to install the relevant software dependencies. A copy of the experimental code will be made publicly available.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Gree Fine-Grained Analysis of Op- timization and Generalization for Overparameterizee Two-Layer Neural Networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 09-15 Jun 2019a.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Process- ing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8139-81 148, 2019b.
Peter L. Bartlett, Sébastien Bubeck, and Yeshwanth Cherapanamjeri. Adversarial examples in multi- layer random relu networks. CoRR, abs/2106. 12611, 2021.
Avishek Joey Bose, Gauthier Gidel, Hugo Berard, Andre Cianflone, Pascal Vincent, Simon Lacoste- Julien, and William L. Hamilton. Adversarial example games. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural In- formation P Processing Systems 33: Annual Conference on Neural Information P Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Minn and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. cttt wttp://///o//////o///oo//
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.ned 2018.
Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, and Rémi Tachet des Combes. A single gradient step finds adversarial examples random two-layers neural networks. CORR, abs/2104.03863. 2021.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pp. 39-57. IEEE Computer Society, 2017.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. ZOO: zeroth order optimization based box attacks to deep neural networks without training substitute mod- els. In Bhavani M. Thuraisingham, Battista Biggio. David Mandell Freeman, Brad Miller, and Artificial Intelligence and Se- curity, AlSec @ CCS 2017, Dallas, TX, USA, November 3, 20/7 pp. 15-26. ACM, 2017. doi: 10.1145/3128572.33 14444444..144488.. URL https: /tw. wrg/ooggg/.ooo /00 1 1444 /05///12555// 0105577..114444 3140448
Arunesh Sinha (eds.), Proceedings of the 10th ACM Workshop
Minhao Cheng, Thong Le, Pin- Yu Chen, Huan Zhang, Jinfeng Yi. and Cho-Jui Hsich. Query- efficient hard-label black-box attack: An optimization-aase based approach. In 7th International Con- ference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
10

---

Under review as a conference paper at ICLR 2022
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta (eds.), Advances in Neural Information Processing Systems 22: 23rd Annual Conference Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pp. 342-350. Curran Associates, Inc., 2009.
Alexander G. de G. Matthews, Mark Rowland, Jiri Hron, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. CoRR, abs/1804, 1 1271, 2018.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceed- ings, 2015.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 2142- 2151. PMLR, 2018.
Andrew Iyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neurul Information Processing Systems 32: Annual Conference Neural Informa- tion P Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 125- 2019.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kris- ten Grauman, Nicolò Cesa-Bianchi, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8580-8589, 2018
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings, 2017
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Confer- ence Track Proceedings. OpenReview.net, 2018.
Jachoon Lee, Lechao Xiao, 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 H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Qizhang Li, Yiwen Guo, and Hao Chen. Practical no-box adversarial attacks against dnns. CoRR, abs/2012.02525,, 2020. URL
02525
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial exam- plcs and black-box attacks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference Learning Representations, 2018.
Seyed-Mohsen Moosavi-Dezzool Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 2582. IEEE
Computer Society, 2016.
11

---

Under review as a conference paper at ICLR 2022
Radford M. Neal. Priors for Infinite Networks, pp- 29-53. Springer New York, New York, NY, 1996.
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang. Jiri Hron, Daniel A. Abo- lafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans. LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababu, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Nicolas Papernot, Patrick D. McDaniel, and Ian J. Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. CoRR, abs/ 01116605777777 2016.
Nicolas Papernot, Patrick D. McDaniel, lan J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Anan- thram Swami. Practical black-box attacks against machine learning. In Ramesh Karri, Ozgur Sinanoglu, Ahmad-Reza Sadeghi, and Xun Yi (eds.), Proceedings of the 2017 ACM on Asia Con- ference on Computer and Communications Security, AsiaCCS 2017, Abu Dhabi, United Arab Emirates, April 2-6, 2017, pp. 506-519. ACM, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, 2014.
Florian Tramèr, Nicolas Papernot, Ian J. Goodfellow, Dan Bonch, and Patrick D. McDaniel. The space of transferable adversarial examples. CoRR, abs/1704.03453,, 2017. URL http:
03453
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In 7th International Conference on Learning Repre- sentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Greg Yang. Tensor programs II: neural tangent kernel for any architecture. CoRR, abs/2006.14548, 2020. Uttttttps://arrt //axxvv org hwtgg//bb///000 14548
Chia-Hung Yuan and Shan-Hung Wu. Neural tangent generalization attacks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12230-12240, PMLR, 18-24 Jul 2021.
A APPENDIX
A.1 DERIVATION OF ADVERSARIAL PERTURBATIONS
A.1.1 PERTURBATIONS OF UNSEEN TEST DATA
Here give the explicit expression of the matrix A the case of unseen test data:
V hx,, X1 )
V 1xx; )² )
A A = m
(16)
Vx, Xx,,,(,,,,))
A.1.2 MULTICLASS DERIVATIONS
Here derive the expressions for Eq.
While we remain with X E Rnd the other quantities change as y E Rnk f(X) E Rn and
H(Y, X¹) E Rakxnk i.e. for each data pair (x,, x,) have H(x,, X;) Rkkk Let H (x;,
12

---

Under review as a conference paper at ICLR 2022
denote the entry of (x;, xy) that corresponds to the I-th and the m-th output of the model (evaluated at x; and xy). Then, with similar reasoning that led to Eq. (5) we now obtain:
Him (x; + 7) xj) R Him (Xi, x,) Vx; H Im (x,, xj)n.
(17)
For the prediction of the model on the whole dataset, we have:
f(X) =++
H))
(18)
which for given sample x; gives:
f(x: + m:) = Yi
+4 1n( ()) y,,
(19)
ER
where (i-1))skk; equal
ERakxd
(Vx. HI
Vx. (x,,xx)
V x: (x,,)x)
Vx xi H H xx)) 77:
(Vx, H21 (1)
Vx, (x,,,,,,
Vx, H21 X2)
x, H (x,, (,,, xn)) 17:
(Vx, HAi (x,,,,
xx (x,(x
Vx, (x;,
Vx (x,, xx))
ERkxnk
(20)
Derivation of Max-of-l1 perturbation: attacks (see e.g. Carlini & Wagner (2017), we solve:
Similar in spirit to traditional approaches in adversarial
arg max max m Ser=
fr(x; + m)) - fr. (x; + m)),
where r* arg y;, ie. chose m such to most efficiently decrease the correct response while maximally increasing one of the false responses. The solution is given by:
Th arg Inll Se rl,,
max on ni 2r-
arg max max nf (z, 2,,) [nlll Sermllmp
(21)
k csgn(arg max ||z, - 2,- 11)..
Derivation of Sum-of-Aa perturbation: For one-hot vectors y; we could, instead, maximize the cross-entropy between the labels and the new outputs, thus choosing to produce maximally mixed output:
e (2) +n
Loe(f +n),,.)
Σ r=1
y log
2p'=1 e
kk
(0) 4nn
cl+n 2,,
log
(22)
Er=Lrae e ny + ell mn a,
log
Σ
which amount maximizing
Σ
th (2. (,,))
13

---

Under review as a conference paper at ICLR 2022
For small perturbations we can develop the exponential to first order" which leads to finding the maximum of
1 Mi
Σ
(zr
2,-))
This yields 7, equal to esgn Exyre (z,, 2,,z) )).
A.2 ANALYTICAL RCF KERNEL
We give the formula for the gradients of the different elements of the NTK for the RCF model considered the experiments.
=
arccos
x x; ||x: |||>||1| |1
)x, +
Vxi
arccos
(
|x,1||>|||
x,
x? Xj
2x
2
2T
xx'x;
arccos
||x: ||1ss
1
xf Xj
)x, +
Xx.
x
2x
x x5
x|
|| ||55|
2TT
-
[|xxa1 [1xs
arccos x² X;
Xy Xy||>;;
|||x||| ||
- xf x3
Xe 11,,,1
||xs
||||||||
}x, +
[xxi
x? x.
2
2x
xx'xx xy 2T - ([xx. -
|[x
||
11x,,
(23)
Note that one must pay attention when evaluating the diagonal entries (or any entry whose corre- sponding vectors are aligned). because the arccos function is not differentiable at 1. To proceed, one has the option to do analytic expansion over 1, and treat this case separately. In practice, truncate all inner products between - -1 6 and 1 - for some small > (e.g. ò= le 5), since found this makes the method numerically stable.
A.3 EXPERIMENTAL DETAILS
A.3.1 SETUP
For all models, we used GPU enabled hardware expedite computational time. Our experiments were performed on a SLURM cluster enabled with NVIDIA V100 Tesla and RTX 8000 GPUs, using the PyTorch package.
In all data sets and all experiments, we drop the last batch if its length is smaller than the others.
RCF Models In all experiments, we set the width m the models equal to 10000 and the variance of the random initialization, x²2 to 0.012. To train the models, we use (full-batch) gradient descent optimizing the quadratic loss with learning rate equal to 0.01. On MNIST, all models are trained for at least 5000 epochs, and then stop training when training accuracy crosses 99.8%. They record test accuracy between 99.17% and 99.91% On CIFAR, we train the model for 200k epochs. For the multiclass experiment on MNIST, train model with the same hyperparameters for 200k epochs. It recorded 97.01% % and 66.74% accuracy on train and test data, respectively. The empirical kernels were approximated using solely one replica of the models per batch. Given that defining network is essentially cost-free (a few lines code without any/much computational cost), we make the decision to draw new random seed at each batch in order alleviate the randomness factor.
We initialize the parameters of the linear layers of the FC networks using the default PyTorch method, i.e. uniform distribution U 4(-vA, v vk), are trained with stochastic gradient descent using mini-batches of 256, optimizing the cross entropy loss. All models are trained to convergence (see Table 5 for accuracies). We estimate the NTKs
Fully Connected Nets
features The models
*The resulting expression for the maximum also holds when developing second order.
14

---

Under review as a conference paper at ICLR 2022
empirically, by defining exact replicas of the models to approximate equation In the smaller nets, we use 3 models initialized with different random seeds for each batch for the approximation, and just one replica per batch on the largest ones (width 10000 and depth equal to 4 or 6). Limited by the heavy computations of the autodifferentiatoon tool to estimate the NTK related quantities, we set batch size equal to 64. The -magniuue of the perturbations is set to 0.3. Due limitations in compute we restrict ourselves to produce results on 20% of the training set.
model
Train
Test
(2, 100)
99.02
97.69
(2, 1000)
99.03
97.94
(2. 10000)
99.01
97.83
(4, 100)
99.05
97.36
(4, 1000)
99.06
97.67
(4, 10000)
99.09
97.73
(6, 100)
99.21
96.52
(6, 1000)
99.51
97.1
(6. 10000)
99.34
97.42
Table 5: Train and test accuracy on fully connected nets (MNIST).
Transferability To generate the NTK-noise we use the sum-of-Az method using mini-batches of size 256 and e = 0.3. All models were trained with stochastic gradient descent on the & loss with batch size
0.01. LeNet 300-100 was trained for 500 epochs, recording at the end of training 99.96% train accuracy and 98.02% on test. LeNet was trained for 250 epochs, recording at the end of training 99 99.82% train and 98. 98.62% test accuracy. ResNet belongs in the family of wide ResNets 50-2, and it was trained for 100 epochs recording at the end of training 99.78% training and 09.29% test accuracy.
256. Learning rate was
PGD attack details PGD attacks as in Eq. 2 optimize the cross-entropy loss for 40 iterations with step size = 0.01 on MNIST and a = 2/555 on CIFAR.
A.3.2 COMPARISON OF DIFFERENT MULTICLASS ATTACKS
Here we compare the max-of-t1 and sum-of-Az methods for attacking multiple output models as derived in Sec. Sec.3.2 in the setting of the RCF model on MNIST to illustrate our adoption of sum-of- A. First, we evaluate both methods on test data using the analytical kernel with batch size 64 (i.c. using only the first 64 training images), and we obtain 56.47% accuracy for max-of-ly and 42.08% for sum-of-A 22. Then, compare them training data with empirical kernels with batch size 64, obtaining 37.57% and 28.37% respectively. Sum-of- is clearly a better choice for both types of kernel. We performed the comparison in the small batch regime, since this the case of interest in Sec. 4.2 where empirical kernlss are estimated using little data. For larger batch sizes, we found that the methods perform similarly (see Fig. (right) in App. A.3.4).
A.3.3 EMPIRICAL KERNEL RESULTS OF SEC. AND SEC.
Here we provide the results for the experiments on the multitask classification task of MNIST using empirical kernels to compute the adversarial perturbations.
First, it must be noted that we attack the model in batches. If, for example, the batch size is set to 256 then we first calculate the optimal perturbations for the first 256 images using only these images for the kernel expressions H(X,' and A; Eq. 99. then repeat for the next 256 and so on. In the case of training data, we progressively use all the training dataset, but in the case of test set attacks we solety use the first 256 images of the training dataset. This is equivalent to assuming that the model was only trained on this batch of data.
A note to the careful reader: these results are better than the corresponding ones with the analytical kernel, although that is not the case elsewhere (analytical results are always superior). This is attributed to the different approach we take regarding the batch size in train vs test data, which is important with small batch sizes. See the second paragraph of A.3.3
15

---

Under review as a conference paper at ICLR 2022
In Table 6 present results for batch size 256 (column 3) and compare to the random baseline (column 4) on training data. These two results are then presented for the test set (columns and 6).
sum A (256)
random train sum Az test (256)
random test
24.31
77.92 0.03
24.81
77.6 + 0.08
Table RCF multiclass empirical attacks with MNIST.
Table 7 contains the results the transferability experiment of Sec. using empirical kernel estimated with batch size set to 256. The results are inferior to those of Table which is due to the small batch size (see Sec. A.3.4 for ablation study).
noise (train)
RCF
LeNet 300-100
LeNet
WideResNet
RCF
24.31
14.65
39.83
74.47
noise (test)
RCF
LeNet 300-100
LeNet
WideResNet
RCF (train-agnostic)
24.81
14.74
40.54
74.04
RCF
32.25
19.7
48.85
77.38
Table Transfer results on MNIST (train & test) with NTK-noise (empirical kernel with batch size 256) generated from the RCF model with the sum-of-A. Az attack.
A.3.4 BATCH SIZE EFFECT
Section 4 contains experiments that employ both empirical and analytical kernels. However, current computational limitations do not allow a fair comparison between the two approaches, as the em- pirical kernel is being calculated from relatively small batch sizes comprising only subset of the entire dataset. In order to study the effect of batch size on the quality adversarial examples, we hence turn here the analytical kernel with a variety batch sizes.
First, Table presents the trendline for the binary task of CIFAR with the RCF model considered in Sec. 4.1.1. using test data. We observe significant effect of batch size on the success of the attack. For batch size 1500, we see accuracy of 39.05% (which is close to the 46.05% obtained from the
empirical kernel using the same batch size, Table Ip. but as the batch size increases, the success rate of the NTK attack quickly approaches 100%.
batch size
Accuracy
1500
39.05
4000
5.95
7000
1.05
10000
0.45
Table 8: Test accuracy batch size. Binary CIFAR with analytical kernel of RCF
The above study performed with 8/255. To better understand how the batch size affeets the success our method for a variety of e, in Fig. 2 we reproduce Fig. | enriched with curves that correspond
different batch sizes. In Fig. (right) solid lines correspond to sun-of- Az, dashed lines to max-of-11, and all attacks use ana analytical kernels (with the exception of the black line). Notice that in the small batch regimes the sum-of-Az is clearly better strategy for crafting adversarial examples (which is why we adopt in the experiments of Sec. [42]and Sec. 4.3 see also App. A.3.2). but, given more data, the two approaches seem perform equally well.
A.3.5 SCALABILITY
Our experiments with analytical kernels, which computable for wide variety of models, fast, since they require only a few tensor multiplications, even for very large batch sizes (though with growing memory requirements). This is, in fact, additional advantage of our NTK approach.
Most our experiments with empirical kernels where run as sroofs-of-principe on our own non- optimized auto-differentiation tools of PyTorch. The resulting framework computationally slow
16

---

Under review as a conference paper at ICLR 2022
Accuracy
Accuracy
100
60
40
40-
MTK-1508
MTK
20
0.4
Figure 2: Role batch size on the test accuracy for varying &o magnitude noise c. Left: Binary setting CIFAR with analytical kernel. is given in multiples of 1/255. Right: Multiclass setting on MNIST with analytical/empirial kernel. Solid lines correspond to sum-of- Az, dashed lines to max-of-l1.
(even when GPUs are employed), hence not allowing for full experimentation with very large batch sizes. However, going forward, utilization the JAX library (Bradbury et al., 2018) together with the recent Neural Tangents one (Novak et al.. 2020) (as employed for example in the work of Yuan Wu (202T)) will allow the assessment our attacks with empirical kernels on larger models and datasets, thus opening our methods to any architecture without the need for deriving the analytical expressions.
A.4 WHY PGD PERTURBATIONS USE STRICTLY MORE KNOWLEDGE THAN NTK PERTURBATIONS
Comparing PGD attacks with our methods and arguing that the former require more knowledge might be confusing, since the assumed threat models are different. Indeed, PGD attacking network necessitates access to the model and its weights, while in our methods we assume access to the training data (and some information about the model architecture), but not to the model. Hence, the two threat models might seem incomparable. Here, we argue why, for the purposes of this work, this is not the case.
Current research on adversarial machine learning focuses on security paradigm, where threat model is assumed, an attack is proposed, and subsequently a defense is created to mitigate the problem. In order to try to understand the origin of the existence of adversarial examples, it may be useful to abandon the distinction between an attacker and defender and view their generation as one way process. Viewed through this lens, for PGD "attack" (or any "white-box attack"), train a model, the model learns from the data, and then by calculating the gradients of the model, we craft adversarial examples. Notice that this process uses all the information about the data that the model has stored in its weights: it does use the data. One contribution of our work is the observation that the final weights of the model do not contribute to the generation of these examples least for the experiments conducted and those models in the NTK regime). The above elaborates our claim in the main text that a "white-box attack" is strictly more knowledgeable procedure than the ones introduced in this work.
A.5 ADVERSARIAL. IMAGES
Here we provide some sample images from CIFAR and MNIST, perturbed with our methods. The perturbation is computed from the analytical kernel of the RCF model.
17

---

Under review as a conference paper at ICLR 2022
15
20
25
25
30
0-
5-
15
20
20
25
25
30
0
5
15
20
20
25
25
30
5
10
20
25
25
30
30
10
5
10
20
25
25
30
10
20
30
10
30
Figure 3: CIFAR images. Perturbed images (left) and clean counterparts (right). = 8/255
18

---

Under review as a conference paper at ICLR 2022
7
10
10
15
15
25
26
10
2
10
10:
15
25
10
10
20
10
10-
15-
25
25
10
10
20
5
10
10-
20
25
25
10
10
20
5
4
10
10-
20
25
25
10
20
10
20
Figure 4: MNIST images. Perturbed images (left) and clean counterparts (right) from multiclass analytical kernel. c = 0.3
19


Reviews:
[{"review_id": "olZKHcxtVd", "reviewer": "Reviewer_jJ86", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "While the proposed method is interesting and of practical importance, I have several concerns on performance evaluation on technical novelty compared to previous works, which are detailed as follows.\n\n1. The authors mentioned in Sec. 2 that \"To our knowledge, no prior work to ours has yet connected these\ntwo areas to generate adversarial examples, or has exploited the parameter-free description the NTK\naffords to devise attacks that do not require any information on trained model parameters.\"   I don't think this claim is true. In fact, the proposal of using NTK to construct adversarial attacks was already proposed [R1], an ICML 2021 publication. Thought the focus of that paper is on poisoning attack, [R1] also considers data perturbation, and the analysis looks quite similar to the proposed method. Since the perturbation analysis and the use of NTK is largely similar, I suggest the authors provide detailed comparisons to this work and discuss the novelty compared to [R1]. I also think the adversarial perturbation method used in [R1] can be a baseline method to be added in the performance evaluation.\n\n2. Transfer attack without model access is known as \"no-box attack\" and there are several related works as well, but unfortunately the authors did not cite or compare to any of them. \nThe latest no-box attack paper that I know of is the NeurIPS 2020 publication [R2]. I suggest the authors compare to state-of-the-art no-box attacks on the studied settings so that one can better understand the effectiveness of NTK attack.\n\n\n[R1] https://proceedings.mlr.press/v139/yuan21b.html\n[R2] https://arxiv.org/abs/2012.02525\n", "summary_of_the_paper": "This paper proposes the use of Neural Tangent Kernel (NTK) to generate transferrable adversarial examples without access to the target model.\n\nThe main contributions are:\n\n1. The derivation of adversarial perturbation under NTK setting.\n\n2. Illustration of different attack scenarios using NTK-attack (e.g. no training needed but several initializations, training-data-agnostic, etc).\n\n3. Good transferability performance on MNIST and CIFAR-10 on the tested model compared to PGD attack (Table 4).\n\n====== Post-rebuttal feedback\n\nI thank the reviewer for providing the responses. However, I don't think they address my major concerns.\n\nTechnically, as the reviewer admitted, there is a similar paper published on the same topic (Yuan & Wu, 2021). Although (Yuan & Wu, 2021) focused on poisoning attacks, the fact that poisoning attack is essentially a bilevel optimization means it actual includes the studied inference-attack on NTK as a special case, by treating the target model as fixed and setting the time to infinity in NTK (as the authors also pointed out). In addition, I don't think doing a first-order approximation then solving the approximated problem is a \"difference\" as the authors' tried to argue; to me, this will lead to a suboptimal solution, not even an innovation.\n\nContribution-wise; applying adversarial attack on NTK at inference time seems a trivial extension of PGD attack, as other reviewers also mentioned. The considered transfer attack does not have a solid demonstration of why the result is significant and does not compare to SOTA transfer attacks in the same setting, like no-box attack. ", "summary_of_the_review": "This paper's idea is interesting, but the main concerns are\n\n1. Technical novelty compared to existing works on existing NTK-based generalization attacks. The authors did not discuss the differences at all.\n2. Lacking performance comparison to state-of-the-art no-box attacks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bejllh-rWJX", "reviewer": "Reviewer_YPLb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper derived a few ways to attack the deep neural networks in the kernel (NTK) regime. This paper derived a few ways to attack the deep neural networks in the kernel (NTK) regime. The authors performed experiments on single-layer models and certain specific deep models on MNIST and CIFAR10 using the proposed attacks.\n\nThe main novelty of this paper is the proposed NTK-based attack, which attempts to connect the theory (what we understand about the large width limit) and practice (whether a deep neural network is robust). However, several weaknesses prevented me from recommending acceptance, detailed below.\n\n(1) Technical novelty: while the reviewer wasn't aware of any NTK-based attacks, the proposed attack is a very straightforward extension of the well-known results (essentially, just simply linearizing the model using the kernel and applying FGSM).\n\n(2) Empirical usefulness: from my reading, I don't think the proposed attack is widely applicable and has a very limited impact:\n\n(2a) The proposed attacks are derived from the (large width, small learning rate) limit of deep networks under *standard* training, i.e. no adversarial training. It is well-known that adversarial training is nearly necessary for adversarial robustness - while both the perturbation derived in section 3 and the models evaluated against in section 4 are not adversarially trained. It may be interesting to see whether the analysis in Gao et al. 2018 about the limit of adversarial training in the large width regime can shed light on the attack of adv-trained models.\n\n(2b) The proposed attacks do not produce a way to better defend against adversaries. It is well-known that attacking DNNs is much easier than defending, so finding a new attack is much less interesting than finding a new defense.\n\n(2c) The experiments in section 4 are evaluated against \"toy\" models that are very different from near-SOTA models like TRADES and its variants. As mentioned in 2a, none of these models are adversarially trained. \n\n(2d) Other technical limitations: e.g. all of the models in section 4 are binary-classification models; some of the results require the adversary to have access to the training data/labels, etc.", "summary_of_the_paper": "This paper derived a few ways to attack the deep neural networks in the kernel (NTK) regime. The authors performed experiments on single-layer models and certain specific deep models on MNIST and CIFAR10 using the proposed attacks.", "summary_of_the_review": "I vote for rejection since I don't think the technical novelty and empirical usefulness of the results have reached the level of ICLR paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RZ2U0JFarv5", "reviewer": "Reviewer_BKjF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is clearly written and the contributions well put into context of existing research. The motivation as well as the line of argumentation are well chosen. The authors first describe the challenges with current attack-models in the white- and black-box setting and motivate why NTK based adversarial attacks are able to circumvent these challenges. They do briefly address the shortcomings of NTK-based attacks, needing access to the training data and labels and defer detailed studies on how to address these shortcomings with test data and pseudo-labels  to subsequent work. The authors give theoretical background on how to think about the NTK attacks and how to choose the ideal NTK attack in the binary- and multi-class classification setting based on a first order Taylor expansion of the closed-form NTK. The math appears sound and well presented with more details presented in the appendix. To validate the theoretical argumentation the authors provide experimental evidence on MNIST and CIFAR-10 for a variety of models (mentioned above) that fall within the limit of NTK and far away from the NTK regime and show that at least anecdotally these attacks can work and transfer to other models.\n\nWhile the line of argumentation is well chosen, this reviewer has a few open questions about the solidity of the argumentation. \n- To begin with it is unclear why a first order Taylor expansion is sufficient for the NTK attacks being considered here. It would be good to understand the theoretical assumptions that need to be made in order to show that the first order correction is always finite and non-vanishing  and at the same time dominating the second order corrections. \n- While the sufficiency of the first order correction is shown before based on proofs of Chizat et al. https://arxiv.org/abs/1812.07956, these proofs only apply to the weights of the networks not the inputs. As a consequence the generalization to first order only input corrections are not obvious.\n- Moving on to the experimental validation, the reviewer wonders about the validity of the empirical NTK underlying the data in Table 1. Looking at the vast performance differences between the analytical and empirical NTK it would be good to see a trendline for the empirical kernel as a function of batch-size to see that the empirical kernels indeed do converge to the analytical one. This is important (i) as a sanity check for the experimental procedure and (ii) an understanding of how computationally costly the empirical NTKs are for a given attack success-rate. Especially point (ii) is important when comparing to black-box query attacks that have high sample complexity to approximate the empirical gradient. \n- Looking at Figure 1 the differences between NTK-based and PGD-based attacks are stark. While it is to be expected that the PGD-attack will always be dominant, this reviewer wonders about the different contributions to the gap. To be more specific: what are the effects of the imperfect  empirical NTK due to finite sampling size  and how much does neglecting the second-order contributions to the Taylor expansion contribute? Could this gap be closed by incorporating either of the two? As an intuition the  gap should certainly be close to zero if the empirical kernel is close to the analytic one and we consider 1-step PGD.\n- Looking at Table 3, this reviewer is concerned about some uncommented trendlines: Looking at depth=2 the NTK success-rate diminishes with increasing width. At depth=4 the performance shows a goldi-lock behavior as a function of width, while the trend at depth=6 is the opposite of depth=2. It seems like there are some unexplained patterns and the authors should address this through either theory or more experimental ablations.\n\nFinally some minor points for improvements:\n- The authors state at several occasions that they study the effects over several random seeds. If so, they should also report and plot uncertainties in all places or clarify which experiments have been run with random seeds. So far this is only done in the binary-MNIST case of Table 1.\n- It would be helpful to the reader if the unperturbed baselines would be reported in Table 4 as well to put the attack strength into context.\n- While the authors clearly defer the study of efficacy of test-data with pseudo-labels for NTK-based attacks, it would be good to state why the authors believe this approach to work. As of now there is no reason to believe the attack will work in this setting, putting serious restrictions on the efficacy of the NTK-based attack.\n- Finally, a different way to view these results is through the lens of verifying/falsifying NTK theory. The approach to NTK theory is novel and intriguing and can lead to interesting new findings. In this light, however, this reviewer would like to challenge the notion that the findings are so unexpected: IF NTK theory is valid then many networks learn a similar kernel in the limit. Finite-size corrections should be small and hence NTK-based adversarial samples should be able to fool a range of models that are a finite-size correction away from the NTK limit. On the other hand, if the findings do contradict NTK theory, then this will lead to intriguing new paths of research to understand the breakdown of this theory.\n", "summary_of_the_paper": "In this paper the authors introduce and study a new approach to generate Adversarial Attacks for image classification models. The core of their approach lies in leveraging Neural Tangent Kernel (NTK) formulations of Deep Neural Networks. By using the analytic and empirical NTK versions of common network architectures they are able to generate adversarial samples without requiring white- or black-box access to the model under attack. The work establishes a new link between formerly disjoint research fields of Adversarial Attacks and NTKs.\nThey show empirically that attacks generated using a simple model with closed-form, analytic NTK transfer reasonably well to other models that are far from the kernel regime. In addition they also study the adversarial samples generated from an empirical, sampled kernel via auto-differentiation and show their success in attacking other models.\nThe authors provide ablations on MNIST and CIFAR-10 for standard models such as the analytically solvable Random Combination of Features and deep models such as Fully Connected Networks and Convolutional Networks in the LeNet-family.", "summary_of_the_review": "In summary, the paper introduces a new type of adversarial attacks, based on NTKs and exploiting the transferability of adversarial samples between models. The authors clearly motivate the relevance of their work and chose a suitable line of argumentation consisting of theoretical as well as empirical evidence. However, this reviewer is missing some rigor in the theoretical underpinning as well as the experimental ablation. The work leaves open a few key questions about the validity of arguments, specifically the connection between the NTK limit and the models far away from the NTK limit,  and as of this point shows anecdotal evidence of the method being generally applicable. This is heightened by the fact that the authors are looking at very special datasets as well, MNIST being small and relatively easy and CIFAR-10 being small and complex. It is unclear how these attacks would fare on larger, production-scale models, trained on, e.g., Imagenet. Specific points to improve upon are:\n1. Solidify the theoretical underpinning by providing intuitions and argumentations, possibly proofs, why the second order contributions are negligible\n2. Show that their experimental setup indeed can reproduce the analytical kernel by doing ablations with respect to the sample size and show that the kernel tracks towards the limit and at what cost.\n3. Addressing points 1 and 2 can then give some understanding of the contributions to the gap in performance between PGD and the empirical NTK-based attack curves\n4. Provide some understanding / insights about the different scaling directions of table 3, i.e. why do the directions reverse order as depth increases\n5. Give some intuitions / early evidence why this work would translate to test-data with pseudo-labels, as this is the most likely and relevant scenario in practice.\n\nBased on these observations this reviewer cannot recommend the publication of this work, despite its very intriguing line of research.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JwTHhrsfWD", "reviewer": "Reviewer_ttzq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "My main concern with this paper is that its threat model is not clearly formulated, and in fact, is confusing. For example, when the paper says \"Recall that PGD is a strictly more knowledgeable attack with access to the model parameters.\" this is not correct -- the threat model in this paper is in fact incomparable with the usual threat model in white-box attacks: The reason is that, for a big part of this paper, we assume that the adversary can access the training data (but not model parameters), but PGD attacks can access model parameters (but not training data).\n\nAccessing training data is actually arguably even more knowledgeable -- as an example to this end, the whole field of differential privacy for ML is to study how to release a model, but where one clearly cannot access training data (then no guarantee whatsoever is there). Also, if an adversary can access training data, he can always retrain the model using that training data, and then PGD attack it. So I think allowing accessing training data is really strong.\n\nNow this has left the choice of \"training agnostic\" method in this paper. However, now to this end when I look at empirical results in Table 4 on test data, then PGD (ce) is much better than NTK attacks. So I don't think I will buy the story that NTK attacks are really strong.", "summary_of_the_paper": "This paper investigates to use NTK as a proxy to generate adversarial examples for neural nets. I like the paper in general. The derivations are clear and the experiments are clearly presented. However, I think this paper suffers significant problems from unclear formulation of the threat model.", "summary_of_the_review": "A clear formulation and correct analysis of the threat model is one of the most important things in this kind of work,\nand this work is somehow very confusing in this regard. Even though it has other merits, I'd recommend reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FyBk5cX5b_P", "reviewer": "Reviewer_CStK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The major concerns are as follows,\n\n(1) I am afraid that It is difficult for the proposed method to scale to larger models and datasets, which restricts its application in practical black-box attacks.\n\n-(1.a) On a real-world dataset, the number of training data is extremely large (e.g., millions for ImageNet-1k). However, I conjecture that the proposed requires the full training data to craft adversarial perturbations since the absence of full data on CIFAR-10 is devastating as discussed in Section 4.1.1.\n\n-(1.b) The method seems to be extremely slow. Even if crafting a single adversarial example, we have to calculate gradients for every training sample with respect to random parameters, and then average the results over differently sampled parameters according to Eqn. (3). The number of training samples is large. Besides, I guess the number of sampling might be larger due to the low sampling efficiency in extremely large parameter space (e.g., ResNet-50 on ImageNet). This is almost prohibited. \n\n-(1.c) The CIFAR-10 empirical results are only based on toy models, much smaller than commonly-used models like VGG-19 or ResNet-18, which can't convince me.\n\n(2) Since this paper never proposes a practical attack method nor helps me understand adversarial attacks deeper, I am afraid this paper lacks contributions to the field of adversarial examples.\n\nI am a researcher who mainly focuses on adversarial examples and is unfamiliar with NTK. If any reviewer or the authors could convince me that this paper contribution enough to NTK, I would be glad to reconsider my rating.", "summary_of_the_paper": "This paper proposes an adversarial attack that does not require any access to the model under attack or any trained replica of it with the help of NTK. The authors only demonstrate the effectiveness of the proposed method on small data and toy models.", "summary_of_the_review": "Although this paper explores an interesting problem, the proposed method is almost infeasible and the contributions are really limited. As a result, I don't think this paper achieves the requirements of ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper relies on the analytical tools afforded by on the NTK theory to proposes an adversarial attack that uses the information of the model structure and training data, without the need to access the model under attack. While the reviewers found the problem interesting and well motivated, they feel that the theoretical analysis and the experimental results can be significantly improved. In particular, some of the points that the reviewers did not find convincing during the discussion include: (1) the technical novelty of the work, i.e., applying adversarial attack on NTK at inference time seems a trivial extension of PGD attack; (2) authors' argument that knowing the model is strictly stronger than knowing the original training data; (3) scalability and generalization of the proposed method to settings without training and test set; and (4) comparison to existing sota transfer attacks in the same setting, like no-box attack. Addressing the above points will significantly improve the manuscript.
Decision: Reject