Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness

Summary

The paper studies the problem of adversarial robustness in multi-class classification. The authors show that a necessary condition for the existence of an adversarially robust classifier is the condition that at least one of the class conditional ditributions is "concentrated" in the sense that most of the probability mass is concentrated on a set of very small volume. The condition of concentration however is not sufficient for the existence of a robust classifier, because one also needs the class conditional ditributions to be well-separated. The authors then study adversarial robustness for the special case of data distributions lying on a low-dimensional linear subspace. For this case, they show that robustness at any data point can be certified in a polyhedron that depends on the subspace representation of the point. Using experiments on MNIST dataset, they show that the polyhedron certificate can be complementary to the spherical certificate one can get with randomized smoothing.

Strengths

- Necessary condition: The theorem showing the necessity of concentration for robustness results from a simple, but nice application of the Brunn-Minkowski inequality. I think this condition is novel, and complements existing results showing concentration of measure is bad for robustness - Polyhedral certificate: The theorem showing the polyhedral certificate for robustness appears non-trivial and interesting. The certificate obtained is complementary to the spherical certificates of randomized smoothing. - Writing: The paper is well-written and clear for the most part.

Weaknesses

- Definition 3.1: I think the definition of strongly concentrated distributions is a misnomer. The critical assumption in this definition is in line 125 which assumes minimal overlap between the approximate supports of the class conditional distributions. Hence, this definition has more to do with "well-separatedness" of class conditional distributions, and in my opinion, has very little relation to concentration. - Novelty of the sufficient condition: If concentration on small volume sets is not sufficient for robustness, what is? As I state in the previous point, it is some notion of separation between class conditional distributions. Several papers already study such conditions. For example, [this](http://proceedings.mlr.press/v119/pydi20a/pydi20a.pdf) and [this](https://proceedings.neurips.cc/paper/2019/file/02bf86214e264535e3412283e817deaa-Paper.pdf) paper show that if the class-conditional distributions are well-separated in an optimal-transport distance, then there exists a robust classifier. It is also shown in these papers that such a separation condition holds empirically on real-world datasets. - The low-dimensional linear subspace assumption: First, I think this is a very strong assumption that real world datasets probably don't satisfy. Second, the motivation for studying distributions of this form appears weak, as one can imagine many other types of distributions that satisfy the necessary and sufficient conditions of sections 2 and 3 but are not supported on linear subspaces. Case in point is Example 3.1 in this very paper. - The utility of polyhedral certificate: Intuitively, one can imagine many "benevolent perturbations" to input data that do not affect the accuracy of a classifier. Spherical certificates for robustness make sense because the guarantee holds for any possible direction of the adversarial perturbation. A polyhedral certificate is not a "worst-case" certificate in this sense.

Questions

- For $\sigma = 0.04$ (red and green curves) Figure 6 seems to show that the the paper's method gives a worse certificate than randomized smoothing. Is this a typo? - Is it possible to find the radius of the largest $\ell_p$ ball centered at x that fits inside C(x)? This will give a data-dependent spherical certificate at each point, which will be interesting. Minor suggestions: - I think it is better to show the dependence on dimension for the constants $\epsilon, \delta$ in the main theorems of sections 2 and 3. - The connections of the main theorem of section 4 to subspace clustering literature can probably be presented much earlier. Currently, the paper only brings up this connection at the end of section 4.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

Summary

This paper gives a theoretical insight into the existence of robust classifiers for avoiding adversarial examples, which may be a potential direction for bridging the gap between human perception and machine intelligence. Specifically, this paper reveals the sufficiency and necessity of data concentration for robust classification. The authors conclude that concentration on small-volume subsets of the input space is the key to avoiding adversarial examples for machine learning. In two experiments, the proposed theoretical results are shown to be effective in improving projected robust accuracy and certified accuracy.

Strengths

- The research problem is quite interesting, and is significant for the development of machine robustness and safety. - This paper is well-organized. The analyses are rigorous and solid.

Weaknesses

- The main theoretical results are based on $\ell_2$-normed adversarial training, whether the conclusions are still applicable on $\ell_\inf$ norm is unknown. - The empirical results are insufficient. The experiments are only conducted on every small dataset, whether the theoretical conclusion still holds on larger natural datasets is unknown. - the conclusion related to subspace training is similar to some existing adversarial training methods, such as [1], [2], which shows that adversarial training on subspace can help alleviate overfitting and improve generalization performance. Is there any difference between these works? [1] Li et al., Subspace adversarial training, CVPR 2022. [2] Li et al., On the adversarial robustness of subspace learning, TIP 2020. - Another question is that whether the subspace preserve training could be applied to transferred adversarial attacks. Could you make several discussions to justify this?

Questions

Please refer to weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are well-discussed. No potential negative societal impact is found.

Summary

The paper shows that adversarial examples can be avoided allowing for robust classification as long as the data distribution obeys certain properties. In particular, they show that the the input data distribution needs to be "well-concentrated" and not overlap too much in order to guarantee the existence of a robust classifier with provable certificates. They support their theoretical guarantees with experimental results on MNIST.

Strengths

1. The problem of adversarial robustness is extremely important and impactful. Further, in the face of hardness results and well known existence of adversarial examples, this is a difficult problem to tackle 2. The authors formalize the notion of "well-concentrated" distributions very well. I think the idea of distribution-specific robustness is well motivated and the right way to approach this problem. 3. I think the paper is well written and the mathematical arguments look non-trivial and sound.

Weaknesses

1. Since this work is primarily a theoretical contribution, I consider this a minor point - I would like to see experimental results done on a few settings larger than MNIST. (say Cifar-10, TinyImagenet) 2. My main concern with the paper is that Definition 3.1 is possibly too strong. It almost seems like the definition is equivalent to creating a robust classifier since it ensures that the different classes are well separated and well concentrated. Is there some way to interpolate between Definition 2.2 and 3.1 which is the minimum assumptions required to guarantee the existence of a robust classifier?

Questions

1. In line 229, do you mean strongly concave? Unless you transform the problem to a minimization problem. 2. The assumption that adversarial perturbations do not take $x$ outside the domain $\mathcal{X}$ seems somewhat unreasonable. Is this really necessary? I agree that this is needed for $f(\bar{x})$ to be well defined, but isn't it even easier to guarantee robustness if it is not defined? 3. The notion of requiring the data distribution to concentrate on an exponentially small volume of the input space looks closely related to the hardness results from Wang et al. "Attack of the Tails: Yes, You Really Can Backdoor Federated Learning". Their results show that adversariabl robustness in FL is provably hard which is the opposite of this work. However, I feel they are somewhat related. Can you comment? 4. In (1), can the definition be changed to $f(\bar{x}) \neq f(x)$? This way robustness and accuracy can be disentangled. It seems somewhat unintuitive that an inaccurate classifier cannot be robust. I would expect that the $0$ classifier is the most robust. 5. I have perhaps missed this, but I couldn't find any discussion of the computational cost of certifying robustness using this approach. I would like to see the dependence on $d$. 6. In Figure 5, the "Ours Certified" line is 1.0 for all $\epsilon \in [0, 1]$. However, the certified region should not be symmetric around $x$, so this doesn't make sense to me.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors discuss some of the limitations of their work in Section 6. But I would like them to consider some of my questions above and include those as well if they are relevant.

Summary

This paper first studies the existence problem of a robust classifier from a data concentration perspective. In particular, they prove that the (strong) concentration property of class-conditional data distributions characterizes a sufficient and necessary condition for determining whether a robust classifier exists. This seemingly contradicting result complements existing works on impossibility results of adversarially robust classification [17, 43, 11]. Built upon the assumption that the underlying distribution is concentrated on a union of low-dimensional linear subspaces, the paper proposes a new way to derive robustness certificates by leveraging techniques from sparse representation and subspace clustering. Experiments on MINST are provided as empirical evidence supporting the effectiveness of the proposed certification method.

Strengths

The theoretical results are mostly well-written, and their implications are discussed in detail. I did not check the proof, but I think the results are technically correct. In addition, I very much like how this paper structures its theoretical results: a main theorem followed by a proof sketch and a detailed discussion of its implication. The first part of this paper shows a somewhat surprising result compared with existing works deriving impossibility results of robust classification [17, 43, 11]. Assuming a robust classifier exists (i.e., a human classifier), the paper shows that the data distribution has to be concentrated in a small-volume subset in the input space. A robust classifier is guaranteed to exist if the class conditionals are both concentrated and well-separated. Given that human is robust to small, adversarial perturbations exists, these results suggest natural data distributions are likely to be concentrated, and existing impossibility results may be due to unrealistic distributional assumptions. The second part of this paper aims to study how to leverage the underlying data structure (i.e., the fact/assumption that data are concentrated on a union of low-dimensional subspaces) for adversarially robust classification. The presented method uses the classical literature of sparse representation, which seems novel to the field of robustness certification. Overall, the paper did a good job of discussing their theoretical results and explaining their broader implications.

Weaknesses

Regarding the first part of the paper, I think the presented theoretical possibility results are correct, which complements existing works [17, 43, 11]. However, I want to point out several missing references [1-4]. These works studied the concentration of measure phenomenon and its connection to robust classification/learning. There are some differences, but I believe those existing works are very relevant, thus, should be cited and discussed properly. In particular, your definition of (strongly) concentrated distribution and the notion of concentration of measure introduced in [2] seems different. Also, a key assumption imposed in them [1-4] is that there exists a ground-truth classifier (i.e., a human classifier) and a machine learning classifier is imperfect (see the definition of intrinsic robustness introduced in [3]). In other words, they assume a constant (say 1%) clean error of any machine learning classifier always exists. However, this assumption seems not to be considered in this work. Could you discuss those differences with comparisons to your work? [1] The Relationship Between High-Dimensional Geometry and Adversarial Examples. Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, Ian Goodfellow. ArXiv: 1801.02774. [2] The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure. Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad Mahmoody. AAAI 2019 [3] Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness. Saeed Mahloujifar, Xiao Zhang, Mohammad Mahmoody, David Evans. NeurIPS 2019 [4] Understanding Intrinsic Robustness Using Label Uncertainty. Xiao Zhang, David Evans. ICLR 2022 In addition, I am a little confused about the degree of concentration implied by Theorem 2.1. Theorem 2.1 says that if an $(\epsilon, \delta)$-robust classifier exists, all the class conditionals are $(\epsilon, K\delta)$-concentrated if they are balanced. This result seems interesting, but from my perspective, a discussion of whether this result holds for most data distributions or only applies to certain distributions is missing. Simply judging from Definition 2.1, there is little clue on what data distribution is concentrated and, more importantly, their degree of concentration. The constants $c_1$ and $c_2$ are vaguely described, so could you explain their dependence on other parameters such as the density function q and $\delta$? If the data distribution lies on a low-dimensional manifold, does it always imply the underlying distribution is concentrated? I recommend the authors provide examples of concentrated distributions with a characterization of their degree of concentration. The result of Theorem 3.1 is not very surprising. The assumption that the underlying class conditional distribution is strongly concentrated seems strong. To be honest, I am not convinced that this assumption will hold for natural image distributions. Otherwise, image classification would be rather a simple task. Therefore, it would be important for the authors to clarify this in the response. Regarding the second part, I have to say I am not familiar with the literature on sparse representation. I can understand the motivation and main message of leveraging the underlying data structure, which is interesting. Still, I am concerned about the assumption that data distributions are concentrated on a union of low-dimensional linear subspaces to be too strong to hold in practice. The applicability of your method seems to be heavily dependent on whether the distribution satisfies the imposed subspace assumption. MNIST may be more aligned with such an assumption, but Gaussian-like data distributions such as CIFAR-10 and ImageNet may not be. Therefore, I am not confident that the proposed method will work for other image benchmarks like CIFAR-10.

Questions

1. Could you provide a detailed discussion with related works [1-4] and explain why data concentration implies different conclusions about the possibility/impossibility of adversarially robust classification? 2. If we assume a human classifier is adversarially robust to image classification tasks, does Theorem 2.1 implies how concentrated the input distribution is? If so, what are the important factors affecting the degree of concentration? 3. Do the constants $c_1$ and $c_2$ in Definition 2.2 depend on the underlying density $q$ and $\delta$? If so, could you specify their dependencies? 4. Could you clarify the generalizability of the proposed certified defense in Section 4 if the underlying data distribution deviates from the imposed assumption regarding linear subspaces?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper discusses the limitations and implications of their results well in Section 6.

Thank you!

I thank the authors for their detailed response and for answering all of my questions. I am satisfied with their justification of Definition 3.1 and additional experiments. I also agree with their discussion on (1) vs consistency. I am increasing my score to 8 and recommend acceptance of this paper. I think it is well written and a good contribution to the research area. I would also ask that the authors incoroporate these additional discussions in the final manuscript.

Thanks for the detailed response

I appreciate the detailed clarifications and the additional CIFAR-10 experiments. They clarified my questions and demonstrated the contribution of your work to the field. I will raise my score to reflect this, and I expect to see the above discussions integrated into the next version of your paper.