Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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.

The 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.

(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).

(2) Empirical usefulness: from my reading, I don't think the proposed attack is widely applicable and has a very limited impact:

(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.

(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.

(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. 

(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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: The major concerns are as follows,

(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.

-(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.

-(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. 

-(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.

(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.

I 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
They 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.
The 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.
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.

While the line of argumentation is well chosen, this reviewer has a few open questions about the solidity of the argumentation. 
- 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. 
- 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.
- 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. 
- 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.
- 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.

Finally some minor points for improvements:
- 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.
- 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.
- 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.
- 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.

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:
1. Solidify the theoretical underpinning by providing intuitions and argumentations, possibly proofs, why the second order contributions are negligible
2. 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.
3. 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
4. Provide some understanding / insights about the different scaling directions of table 3, i.e. why do the directions reverse order as depth increases
5. 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.

Based on these observations this reviewer cannot recommend the publication of this work, despite its very intriguing line of research.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

The main contributions are:

1. The derivation of adversarial perturbation under NTK setting.

2. Illustration of different attack scenarios using NTK-attack (e.g. no training needed but several initializations, training-data-agnostic, etc).

3. Good transferability performance on MNIST and CIFAR-10 on the tested model compared to PGD attack (Table 4).

====== Post-rebuttal feedback

I thank the reviewer for providing the responses. However, I don't think they address my major concerns.

Technically, 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.

Contribution-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. 
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.

1. The authors mentioned in Sec. 2 that "To our knowledge, no prior work to ours has yet connected these
two areas to generate adversarial examples, or has exploited the parameter-free description the NTK
affords 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.

2. 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. 
The 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.


[R1] https://proceedings.mlr.press/v139/yuan21b.html
[R2] https://arxiv.org/abs/2012.02525

summary_of_the_review: This paper's idea is interesting, but the main concerns are

1. Technical novelty compared to existing works on existing NTK-based generalization attacks. The authors did not discuss the differences at all.
2. Lacking performance comparison to state-of-the-art no-box attacks.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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).

Accessing 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.

Now 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_review: A clear formulation and correct analysis of the threat model is one of the most important things in this kind of work,
and this work is somehow very confusing in this regard. Even though it has other merits, I'd recommend reject.
review_title: null

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