Adversarial Attacks as Near-Zero Eigenvalues in The Empirical Kernel of Neural Networks

Remark: As mentioned in Section 7, the theoretical result only covers limited neural network architecture, i.e., fully connected layers.

Answer: As pointed out in the response to Reviewer DyBR and as indicated also in Section 7, our results can be seamlessly extended to any architecture where the feature map exhibits Lipschitz continuity.

Remark: DeepFool algorithm is an old attack algorithm and cannot represent all the existing attacks (that are likely to be more powerful than DeepFool). The authors should perform similar experiments with other attack methods.

Answer: As pointed out in Section 7, additional experiments would indeed be beneficial. Please note, however, that our theory is independent from the characteristics of the data as well as of the adversarial attack method. We chose DeepFool as a widely-known algorithm simply for illustrative purposes. The power of the attack method does not affect our theory: as long as one is able to find an adversarial example for the task at hand, it can be described by our framework.

Question: I cannot understand the reason for the assumption on the layer widths, i.e., all layers except the last layer have the same width $N$, because the proof mainly uses the empirical feature map that does not involve the intermediate layer output. Is this assumption necessary for the theorem? If so, how do you justify the assumption on the layer width?

Answer: You are correct in noticing this unnecessary simplification, which was in place only to avoid cumbersome notation. As already mentioned, our theory applies to any neural architecture where the feature map exhibits Lipschitz continuity.

Remark: The limiting process of $\epsilon \to 0$ in the definition of an adversarial example seems flawed.

Answer: Please check our general remark to all reviewers and the corresponding modifications in the paper. Do not hesitate to ask should these modifications not adequately address your comments.

Remark: Assuming that my understanding of the limiting process is correct, the paper has rediscovered the robustness-accuracy trade-off as depicted in A (this is not a critique exactly). Zhang et al. in A propose that adversarial examples and natural samples overlap in the input space and that is why we observe a trade-off between robustness and accuracy in adversarial training. I think the paper should at the very least mention A. An alternative to the proposal of Zhang et al. that might be relevant is B.

Answer: Thank you for pointing out these references. These potential connections are indeed interesting and worth exploring. Please note, however, that the focus of our work differs from that by Zhang et al., as we give a mathematical justification as to why adversarial examples are rarely sampled by chance in practice, even if they "overlap with natural samples".

Question: The limiting process that constructs $\int_t^\infty \frac{1}{\lambda^2} \mathrm{d} \mu (\lambda)$ appear to be a Riemannian sum. However, I am curious to know if $M \to \infty$ is the same as asserting that the size of the training set approaches infinity.

Answer: Here, $M \to \infty$ refers to the infinite sum in the Mercer's decomposition theorem. This infinite sum is well-defined regardless of the size of the dataset.

Remark: It seems that in Theorem 1 the bound on $\epsilon$ in the limit statement depends on the choice of adversarial example $\mathbf{x}'$ which means the asymptotic guarantee would not uniformly hold for all $\epsilon \leq \epsilon_0$ with $\epsilon_0$ being independent of adversarial example.

Answer: In Theorem 1, the possible adversarial examples $x'$ depend on the choice of $\epsilon$, not the other way around. Hence the asymptotic guarantee does hold uniformly for all $\epsilon \leq \epsilon_0$ with $\epsilon_0$ independent of the adversarial example.

Questions: a) In the definition of adversarial examples, what is function $f (\epsilon)$? The definition does not specify function $f$ and only states the condition $\lim_{\epsilon \to 0} f (\epsilon) = \infty$, which would be problematic because for a fixed $\epsilon >0$ we can always find a function $f$ for observed data that makes the definition hold for a perturbed $\mathbf{x}'$. Also, in the proofs of Theorem 1,2 do the authors determine the function $f$ based on the dataset $\mathbf{X}, \mathbf{y}$ or is the choice of $f$ independent of $\mathbf{X}, \mathbf{y}$?

Answer: Please check our general remark to all reviewers and the corresponding modifications in the paper. Do not hesitate to ask should these modifications not adequately address your comments.

Question: In Theorem 1, what is the definition of $p_{\mathbf{X}'}$ (with the prime)? Is it the delta function on $\mathbf{x}'$ or a continuous density function related to data distribution $p_{\mathbf{X}'}$?

Answer: The definition of empirical probability distribution for a dataset is provided in Section 2 at the end of the paragraph on empirical feature maps; it is essentially a summation of Dirac deltas. It's important to note that this definition is generic, and applicable to any design matrix (in particular to $\mathbf{X}')$. The notation $\mathbf{X}' = \mathbf{X} : \mathbf{x}'$ represents the concatenation of matrix $\mathbf{X}$ and vector $\mathbf{x}'$, as described also in Section 2.

Question: I wonder what the authors precisely mean when they say "In the limit $\epsilon \to 0$, .... " in Theorems 1,2. Does that mean there is an $\epsilon_0 > 0$ independent of the choice of $\mathbf{x}'$ such that the statement holds for every $\epsilon \leq \epsilon_0$?

Answer: It implies the existence of an $\epsilon_0$ such that the statement holds for all $0 <\epsilon \leq \epsilon_0$. The possible choices for $\mathbf{x}'$ depend on $\epsilon$, but not the other way around.

Question: What is the mathematical definition of "such that $|| \mathbf{x}^* - \mathbf{x}' || \leq \epsilon$ for some example $(\mathbf{x}^*, y^*) \sim p$. "? If $p$ is a continuous distribution, then every point in $p$'s sample space has zero probability so whether $(\mathbf{x}^*, y^*)$ is in the support set of $p$ or not does not change its zero likelihood to be sampled from $p$.

Answer: Each individual point has probability zero but not a zero probability density. For instance, in a Gaussian density, each real number has a probability of zero when sampled as a specific event; however, it's essential to note that each real number does have a non-zero probability density. The statement $(\mathbf{x}^*, y^*) \sim p$ simply means that point $(\mathbf{x}^*, y^*)$ is sampled according to the same joint probability density $p$ as that of the training data.

Remark: The definition of adversarial examples appears a bit different than the usual definitions, relying on a local limiting assumption. Some work needs to be done to explain the relationship between this paper’s definition and the working definition used of the broader community.

Answer: Please check our general remark to all reviewers and the corresponding modifications in the paper. Do not hesitate to ask should these modifications not adequately address your comments.

Question: Are there geometric interpretations that your theory provides?

Answer: We briefly mentioned the geometric interpretation of our results in Section 6, paragraph 4. We indicated the relationship between the shift towards zero eigenvalues and the shift in the input feature space towards the direction of non-robust features. The latter is a common observation in the literature on adversarial attacks.

Question: Are the authors proposing that this method could serve to identify adversarial examples? If so, is there any contention with [1]?

Answer: In their current form, our results may not be directly applicable for detecting adversarial examples in practical settings. Theorem 1 relies on an abstract test example that the neural network generalizes well to, and such examples are not always accessible in real-world scenarios.

Question: The notation $(x^* , y^*) \sim p$ is strange from a probabilistic perspective. Isn’t there some probability mass on any point $(x^* , y^*)$? It also appears you are assuming no label noise (i.e. the labeling function $y(x)$ is deterministic).

Answer: This notation indicates that $(x^*, y^*)$ is a data point sampled from the same distribution as the training data, with joint probability density $p$. As stated by the reviewer, any point $(x^*, y^*)$ holds a probability mass, and it's precisely with respect to that probability measure that we showed the measure-zero property of adversarial examples. Since $p (x^*, y^*)$denotes a joint probability density, noise can be easily incorporated in its definition.

Question: Is it really necessary to limit this paper to the consideration of fully-connected layers, or is a Lipschitz assumption sufficient?

Answer: Your observation is accurate. As pointed out in the second paragraph of Section 7, our results can be easily extended to encompass other architectures verifying Lipschitz continuity.