Proper Measure for Adversarial Robustness
Authors: Hyeongji Kim
Ketil Malde
Venue:  (2021)
Keywords: adversarial examples
adversarial robustness
adversarial accuracy
nearest neighbor classifiers

Abstract: This paper analyzes the problems of adversarial accuracy and adversarial training. We argue that standard adversarial accuracy fails to properly measure the robustness of classifiers. Its definition has a tradeoff with standard accuracy even when we neglect generalization. In order to handle the problems of the standard adversarial accuracy, we introduce a new measure for the robustness of classifiers called genuine adversarial accuracy. It can measure the adversarial robustness of classifiers without trading off accuracy on clean data and accuracy on the adversarially perturbed samples. In addition, it does not favor a model with invariance-based adversarial examples, samples whose predicted classes are unchanged even if the perceptual classes are changed. We prove that a single nearest neighbor (1-NN) classifier is the most robust classifier according to genuine adversarial accuracy for given data and a norm-based distance metric when the class for each data point is unique. Based on this result, we suggest that using poor distance metrics might be one factor for the tradeoff between test accuracy and $l_p$ norm-based test adversarial robustness.

Under review as a conference paper at ICLR 2021
PROPER MEASURE FOR ADVERSARIAL ROBUSTNESS
Anonymous authors
Paper under double-blind review
ABSTRACT
This paper analyzes the problems of adversarial accuracy and adversarial training. We argue that standard adversarial accuracy fails to properly measure the robust- ness of classifiers. Its definition has tradeoff' with standard accuracy even when we neglect generalization. In order to handle the problems of the standard adver- sarial accuracy, we introduce new measure for the robustness of classifiers called genuine adversarial accuracy. It can measure the adversarial robustness of classi- fiers without trading off accuracy on clean data and accuracy on the adversarially perturbed samples. In addition, it does not favor model with invariance -aaeed adversarial examples, samples whose predicted classes are unchanged even if the perceptual classes are changed. We prove that single nearest neighbor (1 (I-NN) classifier the most robust classifier according to genuine adversarial accuracy for given data and norm- based distance metric when the class for each data point unique. Based on this result, we suggest that using poor distance metrics might be one factor for the tradeoff between test accuracy and 1p norm-based test adversarial robustness.
INTRODUCTION
Even though deep learning models have shown promising performances in image classification tasks (Krizhevsky et al. 2012), most deep learning classifiers are vulnerable to adversarial attackers. By applying carefully crafted, but imperceptible perturbation to input images, so-called adversarial examples can be constructed that cause the classifier to misclassify the perturbed inputs (Szegedy et al. 2013). These vulnerabilities have been shown to be exploitable even when printed adversarial images were read through a camera (Kurakin et al. 2016). Adversarial examples for a specific clas- sifier can be transferable other models (Goodfellow et al. 2014). The transferability of adversarial examples (Papernot et al. 2017) enables attackers to exploit vulnerabilities even with limited access to the target classifier.
Problem setting. In a nonempty clean input set X C. Rdd, let every sample exclusively belong to one of the classes y, and their classes will be denoted as ex- classifier f assigns class label from y for each sample E TRd. Assume is parameterized by 0 and T(0,, x., U) is the cross entropy loss of the classifier provided the input x and the label y E y.
Note that this exclusive class assumption is introduced to simplify the analysis. Otherwise, the definition of adversarial examples (Biggio al. 2013) may not match with our intuition as explained in Section
1.1 ADVERSARIAL EXAMPLES
Definition 1 (Adversarial Example). Given a clean sample x E X and maximum permutation norm (threshold) c, a perturbed sample x' is an adversarial example if x =''ll S and f + c, Biggio et al. 2013).
When exclusive class assumption in the problem setting violated. different oracle classifiers may assign different classes for the same clean samples. (Oracle classifiers refer to classifiers that are robust against adversarial examples (Biggio et al.) 2013) for appropriately large c. Human classifi- cations usually considered as oracle classifiers. For example, while many people assign class for the top right sample shown in Figure [ some people can assign class or because of the ambiguity of that example. If we label data with the most popularly assigned classes, according

---

Under review as a conference paper at ICLR 2021
1
Cree
7
Figure 1: Examples of confusing near image pairs with different classes of MNIST training dataset (LeCun al. 2010). The norms of the pairs are 2.399, 3.100 and 3.131 from left right. From these examples, we can say the exclusive class assumption in the problem setting can be violated.
p(a(c)
Figure 2: Plots of p(z|c -1): red and p(alcc 1): blue for first toy example.
the definition of adversarial example, even some clean samples will be considered as adversarial examples without perturbing the clean samples according to the classifications of some people.
1.2 STANDARD ADVERSARIAL ACCURACY
The following measure is commonly used for comparing different classifiers vulnerability to adversarial attacks (Biggio et al. 20133] Madry et al.) 2017 Tsipras al., 2018 Zhang al. [201)]
Definition 2 (Standard adversarial accuracy).
an indicator function that has value if the condition in the bracket holds and value 0 if the condition in the bracket does not hold. Then, standard udversarial accuracy (by maximum perturbation norm) astd, maz (e) is defined as follows.
Ogtd; max (c) EEEX (f(x*)) c+)] where x mag 1(0,x',cz).
x:: -
1.2.1 ONE-DIMENSIONAL TOY EXAMPLE
Even though standard adversarial accuracy by maximum perturbation norm is commonly used as a measure of adversarial robustness (Biggio et al.) 2013; Madry et al. 2017 Tsipras et al.) 2018 Zhang et al. 2019), is clear whether this measure can be used choose better models. To show this measure is not an appropriate measure of robustness, we introduce the following example.
Let us consider a toy example (see Figure 2 with predefined (pre-known) classes to clean samples in order to simplify the analysis. There are only two classes -1 and 1, i... y {,1, 1}. and one-dimensional clean input set X' [-2, 1) (1,2) S R. e, -1 when æ [-2, 11) and eu when æ E (1, p(c- -1) p(c = 1)
i.e., we assume uniform prior probability.
Let us define three classifiers f1. fo and fs for this toy example (see Figure 3). When step function
if æ
step(x) is defined step(x) -1, x let fi step(x 1), f2(2) = step(x +
4) + step(x), and fa(z) = step(x))
Notice that the accuracy for all three classifiers is 1. However, f1 will not be robust against adver- sarial attacks as points in [1, 1 + c) can be perturbed to change their classification result. fz is overly invariant when
-4. The oracle classifier will be fa-
When the change of standard adversarial accuracies by maximum perturbation norm were consid- ered (see Figure 4) fi shows decreasing standard adversarial accuracy when 1. However,
2

---

Under review as a conference paper at ICLR 2021
f1(w)
f2(#))
fa(#)
Figure 3: Plots of three classifiers. Top: fi()) = step(æ 1). Middle: f2(x) 1 step(s + 4) +
step(2). Bottom: fa(x)= step(x) where step(x)) for 2 0 and step(r) -1 for x < 0.
attd (c)
0.5
aatd maa(c)
a attd maz (az(()) (6)
Figure 4: Change of standard adversarial accuracy for (1x), f2(x) and fz( from top bottom. Observed behaviors of fa and fs will be the same when we compare the adversarial accuracy by maximum perturbation norm
f2 and fa are equally robust according this measure. Thus, the maximum norm-based standard adversarial accuracy function can not tell which classifier is better. (In addition, f1, f2. and fa have the same securacy-Robutnnng the curve for standard adversarial accuracy plot, that is 1.5. This example shows that ARA is also not reliable measure for the robustness of classifiers.)
Area (ARA) (Woods al., 2019),, which measures the area under
1.3 ADVERSARIAL TRAINING
Adversarial training (Goodfellow et al. 2014 was developed to avoid the adversarial vulnerabil- ity of a classifier. It tries to reduce the weighted summation standard loss (empirical risk) E [L(,, -r, y)] and adversarial loss E [L(0, x', y)], i..., aE [L(0, x. v)] (1 a)E [L(9, x', x',y)] where a a hyperparameter for adversarial training, and x' is an adversarially perturbed sample from x with ||~ æ|| < By considering both standard and adversarially perturbed samples, adversarial training try to increase accuracies on both clean and adversarially perturbed samples. In the lit- erature on adversarial training, inner maximization of classifier refers generating adversarial attacks, i.c., generating adversarially perturbed samples x* that maximally increases the loss. And outer minimization refers minimizing the adversarial loss of the model. (Madry et al. 2017) ex- plained that inner maximization and outer minimization of the loss can train models that are robust against adversarial attacks.
However, there is tradeoff between accuracy on clean data and adversarially perturbed samples even when we neglect generalization of classifiers (Tsipras al. 2018 [ohmatob) 2018 Zhang et al., 2019). Hence, when we used adversarial training (Goodfellow et al. (014). we can get classifier whose accuracy is lower than using non-adversarial training method (Tsipras et al. 2018 Santurkar et al.) 2019). Also, Jacobson al. (Jacobsen al. 2019) studied samples whose per- ceptual classes are changed due to perturbation, but not in the model's 's prediction, what they called "invariance-basee adversarial examples." " (These examples also called "type I errors" (Tang al., 2018) or "invalid adversarial examples" (Stutz et al., 2019).) They found that classifiers trained with adversarial training can be more susceptible to invariance-basee adversarial examples. Recently,

---

Under review as a conference paper at ICLR 2021
3
(0.2'4
2
(0,2) 2)
V1
0
(c,0)
-1
2
Figure 5: Two-dimensional sunset dataset class A: red and class B: blue. The colored figure shows that the points on class A resemble the shape of the sun and the points on class B resemble the shape of the horizon.
When consider le norm robustness, the decision boundary of the oracle classifier for this example will be a parabola which satisfies I2 = + where Ii and ø2 represent the first and second axes. dashed black curve. Every point in this parabola has the same distance to the
That is shown nearest sample in class A and B. This oracle classifier can be trained on wwo-dimensional data using non-adversarial training, but in higher dimensional sunset datasets, that might not be possible due to high co-dimension (Khoury& & Hadfield-Mence 2019).
further research showed that there a fundamental tradeoff between adversarial examples (Biggio al. 2013) and invarianee-based adversarial examples (Tramer al. 2020).
1.3.1 SUNSET DATASET
We introduce binary classification problem called sunset dataset. This artificial dataset shows the limitation of standard adversarial accuracy and standard adversarial training method (Goodfellow (et al. 2014) that is intended to maximize standard adversarial accuracy.
This artificial dataset contains uncountably many points. One class (class A) of the dataset is consists of points on a hypersphere. The other class (class B) is consist of points on hyperplane contacting with the hypersphere. One important character of this dataset is that infimum of the nearest distance between the two classes is O.
A two-dimensional sunset dataset is visualized in Figure 5 In that dataset, that classifies points inside the circle classified as class A and class otherwise. The accuracy of the classifier is 1. However, if the maximum perturbation norm > 0, the classifier will always have adversarial examples (Biggio et al. 2013). For example, point (0, 2 2++e) is an adversarial example as it is classified class B according the classifier, and (0, 2) has class A. If try
think of classifier
adversarial
al. 2014). we encounter the problem where point (c, 1 vI e²) (or (1,1) when 2 1), which is on the red circle, can also be considered as an adversarial example originated from 0). (We are considering l2 norm robustness. Visualized points are based on 0.5) If we change the classes of these points to remove ad adversarial examples, we simultaneously introduce invariance-based adversarial examples (Jacobsen et al. (019) on the classifier. If one tries to choose robust classifiers based standard adversarial accuracy with > 0, one would choose classifiers with invariance-basee adversarial examples over the oracle classifier (mentioned in Figure 5). In other words, standard adversarial accuracy can favor classifiers with more invariance-bai based adversarial examples.
training (Goodfellow
2 GENUINE ADVERSARIAL ACCURACY
Definition 3 (Genuine adversarial accuracy). We define genuine adversarial accuracy that uses exact perturbation norm. Note that 1 1() is an indicator function that has value if the condition in the bracket holds and value 0 if the condition in the bracket does not
hold. The complement set of a set S will be denoted as S X the topological clo- sure of X. ie., union of X and its boundary. Voronoi boundary V VB(X) defined as
4

---

Under review as a conference paper at ICLR 2021
{a' E BR & : # -221|=' - x1 || x2ll}- Previously allowed perturbation gion X. defined as { V (B( || - =l1 where 2).
Then, genuine adversarial accuracy (by exact perturbation norm) Ogen; ezact (c) is defined fol- lows.
Ogen; emant (e) S [1 (f(x*) =
where Sexrct (c) {r E X Hrd E E & || - -al1 = and x² arg max B(x 1(0,0', cx) when > O.
Ggen; exect (0) EzEx [1 (f(x)) = cx)] when
The reason for proposing genuine adversarial accuracy is avoid using a point x' Rd more than once when calculating a classifier's robustness. That is shown in Theorem X' is used instead of because using X' can ignore many points the calculation of robustness (see an example in Section A of the appendix). Voronoi boundary (B(2') X') is used in the calculation points on this set can be approached from two different points in X with the same distance, and these points need to be ignored in order to avoid conflicts when measuring adversarial accuracy. Previously allowed perturbation region X, is used to ignore this region for given c. In the calculation of the expected value, Sewaet (c) is used because there may be x' that satisfies new constrain.
Figure shows the result of using genuine adversarial accuracy on the one-dimensional toy example in Section 1.2.1 According this measure, fa is the most robust classifier for given data, and that consistent with the oracle classifier.
Theorem 1. Genuine adversarial accuracy only use each point only once to calculate adversarial accuracy, In other words, it does not allow overlaps.
The proof in Section Cf the appendix. Theorem I indicates that genuine adversarial accuracy avoids the tradeoff between accuracy and (genuine) adversarial accuracy. Also, it no longer favors classifier with excessive invariance, which indicates that does not favor a classifier with invariance- based adversarial examples (Jacobsen et al. 2019). The fact that it does not allow overlaps also matches with our intuitive understanding of the robust classification.
agen: ovact
a.7d
Ogan; ezacs(e) (e)
0.5
2
Ogen: smact (e)
Figure 6: Change of genuine adversarial accuracy agen; exact(e) for (z)). fa(z), and fa(z) by exact perturbation norm from top to bottom. Details for calculation is explained Section of the appendix.
5

---

Under review as a conference paper at ICLR 2021
3
A SINGLE NEAREST NEIGHBOR (1-NN) CLASSIFIER IS THE CLASSIFIER THAT MAXIMIZES GENUINE ADVERSARIAL ACCURACY
Theorem 2. A single nearest neighbor ( (I-NN) classifier maximizes genuine adversarial accuracy, and it is the almost everywhere unique classifeer that satisfies this except for X X and Voronoi boundary V V()).
Proof of the theorem is in Section of the appendix. Note that both Theorem D Jand Theorem 2 only hold for the same data. Thus, Theorem 2 does not imply that a I-NN classifier based on traiing data will be optimally robust on the test data.
4 POSSIBLE FACTOR FOR THE TRADEOFF BETWEEN TEST ACCURACY AND Lp NORM-BASED TEST ADVERSARIAL ROBUSTNESS: POOR DISTANCE METRIC FOR MEASURING ADVERSARIAL ROBUSTNESS
As Theorem 2 only holds for the same data set, it does not directly tell about generalization. Nev- ertheless, it follows from the theorem that the 1-NN classifier on training data will he the optimally robust classifier training data measured by genuine adversarial accuracy. This result gives us an insight that properly applied adversarial training will train models to mimic I-NN classifiers as their training loss try enforce them make the same prediction as I-NN classifiers. The fact that properly applied adversarially trained models can mimic 1-NN classifiers indicates that gen- eralization powers of adversarially trained models might also mimic that of 1-NN classifiers. As I-NN classifiers depend on distance metrics, test accuracy and test genuine adversarial accuracy of adversarially trained models can also dependent on the distance metric used for measuring ad- versarial robustness. If robustness to perturbations on the distance measure is not much related to generalization, is possible that there exists a tradeoff between test accuracy and test adversarial robustness.
We apply two analyses on MNIST (LeCun et al. 2010) and CIFAR-10 (Krizhevsky, 2009) data. In the first analysis, we analyzed different predictions test samples between ver-aaversarrillyy trained models and adversarially trained models to check if adversarially trained models resemble 1-NN classifiers. We measured significance using two-sided McNemar's test (McNemar 1947). We used publicly available models for comparisons. We used PGD-AT (adversarial training with projected gradient descent) (Madry et al. (017) and TRADES (Zhang et al. 2019] models for ad- versarially trained models. In the second analysis, we checked the test accuracies of I-NN classifiers based on training data check globally robust models' generalization powers. to norm-based 1- NN classifiers can take multiple nearest neighbors for each sample. In such cases, we calculated values ignoring these samples and using the class with the largest number of nearest neighbors for prediction. Values obtained by the latter approach are shown in parentheses in the tables. Details of the models and further results are Section DactionGGin the appendix.
On MNIST LeCCun et al. 2010) data, PGD-AT (hx norm, = 255 model showed fewer agree- ments with I-NN classifter than the non-adversarially trained model (shown in Table [I. This result conflicts with the speculation that adversarially trained models mimic I-NN classifiers. However, considering the fact that no significant difference in proportions was found, this could be due to chance. (The fact that non-ad vor-adlersarallly trained model already behave similarly with I-NN classi- fier on test samples, shown in Table Sable5iin in the appendix, could also be contributed to this result.) As shown in Table on CIFAR-10 (Krihevsky 2009) data, adversarially trained models behaved more similarly to 1-NN classifier than non-adversarially trained models on test samples. The differences in the proportions were significant except for PGD-AT (l.c norm, e 8 These results indicate that adversarial training can force models behave like I-NN classifiers in some data. However, the observation that fewer than half of the changed predictions agree with 1-NN classifiers indicates
'"almost everywhere" is a term used in mathematical analysis. If property holds almost everywhere, means the subset of points that does not satisfy the property has measure zero.
?Properly applied adversarial training refers to adversarial training (Goodfellow et al. 2014] with no con- flicting regions originating from overlapping regions. Adversarial training with Voronoi constraints (Khoury & Hadfield-Menel (219)) satisfy this. Standard adversarial training with sufficiently small e can satisfy this.
"Significance threshold 0.01 was used.

---

Under review as a conference paper at ICLR 2021
Table I: Proportions agreements with I-NN classifiers among different predictions on test sam- ples with non-adversarially trained models and adversarially trained models (Engstrom et al. 2019 Zhang al. 2019) for MNIST (LeCun et 2010) training data.
Model
PGD-AT
TRADES (ssc 0.3)
(Distance metric, training
(1ae 0.3)
Non-advensarially trained model
0. 0.1948 (0.3182)
0.129 (0.2407)
Adversarially trained model
0, 0.1039 (0.2597)
0.2037 (0.2963)
p-value
0.05408 (0.3966)
0,4807 (0.711
Table Proportions agreements with 1-NN classifiers among different predictions on test sam- ples with non-ad ail--dderss advesarrrrrrllly trained models and adversarially trained models (Engstrom et al. 2019 Zhang et al. 2019) for CIFAR-10 10 Krizhevsky 2009) training data.
Model
PGD-AT
PGD-A (a
PGD-AT (12
PGD-AT (s nerm.
TRADES (1oc
(Distance metric, training e)
0.25)
0.5)
== 1.0)
0.03137
E = 0.031)
Non-adversarially trained model
0.1529
0.1599
0.1996
0.1231 (0.1261)
0.1064 (0.1103)
Adversarially trained model
0,2562
0,28
0.2948
0,1480 (0. 1518)
0.1795 (0.1878)
10-11
p-value
1.593 10-b
1.500 10
6.403
10-9
0.09110 (0.06525)
(1.008 x 10"!1>
that other factors are involved in the prediction changes. It is also possible that other changes in predictions occurred during the process of making the models behave like 1-NN classifiers as con- volutional neural networks have limited capacities.
As shown in Table 3 I-NN classifiers on MNIST data (LeCun al. 2010) scored high accuracies. However, 1-NN classifiers scored low accuracies on CIFAR- 10 data (Krizhevsky 2009). Using different distance metrics resulted different accuracies both data. These results show that might have to sacrifice generalization performance when seeking global robustness on training data depending on data and distance metrics.
When we combine the results, adversarial training can make models behave like 1-NN classifiers and make other changes. When I-NN classifiers have low generalization performances, I-NN re- sembling adversarially trained models can have reduced test accuracies. Other prediction changes can also contribute to reduced test accuracies.
RELATED WORKS
Wang et al. 2018) showed that 1-NN classifier is non-robust when the exclusive class assumption (in the problem setting) is violated. However, they also showed that, 1-NN classifiers be robust against adversarial attacks under the exclusive class assumption. Based on that result, they proposed robust I-NN classifier that uses subset of the training data whose labels highly confident.
Table 3: The values or ranges of test accuracies of 1-NN classifiers on training data for MNIST [LeCun et al. 2010) and CIFAR-10 (Krizhevsky 2009) data.
Data
MNIST
CIFAR
Metric
la norm
for nomn
l2 norm
Ioe norm
I-NN classifier
0.9677
[0.6142, 0.9662]
0.3539
[0. 1722, 0.2427] (10.1773, 0.2242))
(10.8416, 0.86351)

---

Under review as a conference paper at ICLR 2021
(Khoury& & Hadfield 2019) showed that 1-NN classifiers exponentially fewer sam- ples than standard adversarial training (Goodfellow et al. 2014) to correctly classifies samples on the tubular neighborhood. The authors also suggested an improved adversarial training method that uses Voronoi cell constrains instead of Il-ll constrains.
Under the settings that adversarial perturbations allowed to change classes, (Tiipras al. 2018) and (Dohmatob) 2018) argued that the tradeoff between natural accuracy and standard adversarial accuracy may be inevitable in any classifier. Our work shows that this tradeoff can be avoidable by using genuine adversarial accuracy. Another explanation for the tradeoff is that robust classifi- cations might require more model capacities than standard classifications (Nakkiran) 2019). Based on analysis on linear regression problems, (Raghunathan et 2019) (2200 suggested conditions of data distribution that adversarial training (Goodfellow et al. 2014) can hurt generalization even only class consistent perturbations are used.
CONCLUSION
Even though standard adversarial accuracy is commonly used to measure the robustness of classifiers (Biggio et al. 2013: Madry et al. 2017: Tsipras et al. ZZang et al. 2019), it has problems that allows overlapping regions. In this work, we introduce genuine adversarial accuracy that avoids such a problem. Hence, genuine adversarial accuracy does not have the tradcoff between accuracy and genuine adversarial accuracy unlike standard adversarial accuracy (Tsipras et al.) 2018 Dohma- tob 2018 Zhang et al. 2019). Genuine adversarial accuracy ignores adversarial examples (Biggio et al.] 2013) when applied perturbations are large enough to change classes of classifier (I-NN classifier) as shown Theorem [ Hence, it does not favor a classifier with invariance- adver- sarial examples (Jacobsen et al., 2019). These advantages of genuine adversarial accuracy suggest that graphs of genuine adversarial accuracies of classifiers need to be used for evaluating the robust- ness of classifiers. (In practice, it can be hard to calculate genuine adversarial accuracy by exact perturbation norm. However, one can use genuine adversarial accuracy by maximum perturbation norm explained in Section E of the appendíx.)
Furthermore, in Theorem 2 we prove that a single nearest neighbor (1-NN) classifter is the most robust classifier according genuine adversarial accuracy for given data and distance metric by assuming exclusive class on data distribution. It suggests that adversarial training with Voronoi con- straints (Khoury & HadiilddMMnnell 2019) would train hybrid models that seek optimal robustness on the training data. (For adversarial training with Voronoi constraints, one can also use soft labels explained in Section[Faand Section of the appendix.)
As explained in Section Theorem gives us an insight that models trained by adversarial training (Goodfellow et al. 2014) without overlapping regions can mimic 1-NN classifiers. That was con- fimmed on analysis on CIFAR-10 data (Krizhevsky) 2009). That provides one possible factor why adversarial training might reduce test accuracy and why a tradeoff between test accuracy and test adversarial robustness might exist. As the choice of the distance metric can influence both the gen- cralization power of 1-NN classifiers and the measure of adversarial robustness, one might have to be careful when choosing the distance metrics. In other to achieve both high test accuracy and test adversarial accuracy, distance metrics that are highly related to generalization might be necessary.
FUTURE WORK
Our analysis is based on the assumption that the data satisfy the exclusive class assumption in the problem setting) We also need similar analyses for various conditions that data violate that assump- of the appendix shows a way of speculating optimally robust classifiers when data contain additive input noise.)
tion. (Section of
From Theorem (except for X X and Voronoi boundary V (x))) for given data and a distance metric. In addition, as explained in Section 4 using distance metrics that are highly related to generalization would be necessary to achieve both high test accuracy and test adversarial accuracy. Thus, need to define metric that captures various changes of images so that I-NN classifiers based on that distance metric have high generalization power.
2 we know that there will be an almost everywhere unique optimally robust classifier
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smnić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. Joint European conference machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Akshay Raj Dhamija, Manuel Günther, and Terrance Boult. Reducing network agnostophobia. In Advances in Neural Information Processing Systems, pp. 9157-9168, 2018.
Elvis Dohmatob. Limitations of adversarial robustness: strong No Free Lunch Theorem. arXiv: 1810.00065 [es, stat], October 2018. UKL/ttpp///arr...rrr///////B 04065
arXiv: 1810.04065.
Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019, URL httpt:ttt/tttbbb....b. www.o///waaallla/oooouaaeeeeeeee
Chuanxing Geng, Sheng-jun Huang, and Songean Chen. Recent advances in open recognition: A survey. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
Jacob Goldberger, Geoffrey E Hinton, Sam T Roweis, and Russ R Salakhutdinov. Neighbourhood components analysis. In Advances in neural information processing systems, pp. 513-520, 2005.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 1412.657, 2014.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1321-1330. JMLR. org, 2017.
Jörn-Henrik Jacobsen, Jens Behrmann, Nicholas Carlini, Florian Tramèr, and Nicolas Paper- not. Exploiting excessive invariance caused by norm-bounded adversarial robustness. ArXiv, abs/1903. 10484, 2019.
Pedro R Mendes Júnior, Roberto De Souza, Rafael de O Werneck, Bernardo V Stein, Daniel V Pazinato, Waldir R de Almeida, Otávio AB Penatti, Ricardo da S Torres, and Anderson Rocha. Nearest neighbors distance ratio open-set classifier. Machine Learning, 106(3):359-36,, 2017.
Mare Khoury and Dylan Hadfield-Menell. Adversarial training with voronoi constraints. arXiv preprint arXiv:1905.0100 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv: 1607.02533
[cs, stat), July 2016. URL. http:://arrtwv..o///bb////////// 025333
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecur. www..//w...m//xx////iisssst 2, 2010.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.
Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0688, 2017.
Quinn McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12(2):153-157, 1947.
John Moody and Christian J Darken. Fast learning in networks of locally-tuned processing units. Neural computation, 1(2):281-294, 1989.

---

Under review as a conference paper at ICLR 2021
Preetum Nakkiran. Adversarial robustness may be at odds with simplicity. arXiv preprint arXiv:1901.00532. 2019.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical Black-Box Attacks Against Machine Learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, ASIA CCS '17 pp. 506-519, New York, NY. USA, 2017. ACM. ISBN 978 1-5003444444444 doi: 10.1145/305293333550009 URL http: acm.
305300
Aditi Raghunathan, Sang Michael Xie, Fanny Yang. John C Duchi, and Percy Liang. Adversarial training can hurt generalization. arXiv preprint arXiv:1906 06032, 2019.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. arXiv preprint arXiv:2002.10716, 2020.
Shibani Santurkar, Dimitris Tsipras, Brandon Tran, Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Computer vision with single (robust) classifier. arXiv preprint arXiv:/906.0944 2019.
David Stutz, Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and general- ization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp-
6976-6987, 2019.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6/99, 2013.
Sanli Tang, Xiaolin Huang, Mingjian Chen, Chengjin Sun, and Jie Yang. Adversarial attack type Cheat classifiers by significant changes. arXiv preprint 0rXiv:1809.005000 2018.
Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jöm--eerik Jacobsen. Fundamental tradeoffs between invariance and sensitivity to adversarial perturbations. arXiv preprint arXiv:2002.04599 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint
12152, 2018.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, pp. 3630-3638, 2016.
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In International Conference Machine Learning, pp. 5133-5 51223-514,,, 2018.
Walt Woods, Jack Chen, and Christof Teuscher. Adversarial explanations for understanding image classification decisions and improved neural network robustness. Nature Machine Intelligence, (11):508-516, 2019.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent Ghaoui, and Michael I Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv: 1901108877 2019.
10


Reviews:
[{"review_id": "hlM8nJFPwSS", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new measure called \"genuine adversarial accuracy\" for adversarial robustness of a classifier. The key idea is that 1) they calculate robust accuracy when the perturbation norm is exactly $\\epsilon$, not smaller than $\\epsilon$ like standard robust measures, and 2) each point will not be used multiple times in calculating the robust measure. Their theoretical results say that 2) is really the case, and an 1-NN classifier is most robust w.r.t. the proposed measure.\n\nStrength of the paper\n1. It provides a new robust measure, which potentially provides no trade-off solution for the adversarial robustness, if a distance leading to good generalization is properly chosen.\n2. The information in Table 4 gives good insight of the benchimarking datasets, which can potentially benefit researchers of this literature. \n3. Many interesting insights, such as regular adversarial training may push the model to behave similar to 1-NN classifiers on the training set, if $\\epsilon$ is set small enough. \n\nSome crucial technical flaws are out standing, and the paper is generally hard to read.  \n\nThe key concern about the paper is the lack of clear definitions on the important concepts, and therefore, on the proposed robust measure. The authors may have a clear measure in their mind, but based on the provided definitions, it does not seem clear.\n\n 1. The provided definition of Voronoi boundary $$VB(\\mathcal{X})=\\\\{x'\\in \\mathbb{R}^d|\\exists x_1,x_2\\in \\bar{\\mathcal{X}}:x_1\\neq x_2, \\|x'-x_1\\|=\\|x'-x_2\\|\\\\}$$ seems incorrect, or some examples on which their measure cannot be applied are not properly addressed. At least, I can find an example on which the proposed measure is not applied. For example, let's take a unit sphere as $\\mathcal{X}.$ Consider $\\ell_2$ norm. Then, for any combination of $x'\\in \\mathbb{R}^d$ and $x_1\\in \\bar{\\mathcal{X}}$, we can find $x_2\\in\\bar{\\mathcal{X}}$ s.t. $\\|x'-x_1\\|=\\|x'-x_2\\|$ and $x_2\\neq x_1$ as long as $x'\\neq x_1$. That means, for a unit sphere $\\mathcal{X},$ the Voronoi boundary is the entire input space $\\mathbb{R}^d$. Now, $VB(\\mathcal{X})^c=\\phi$, and therefore $S_{exact}(\\epsilon)$ is not defined or empty in this case. Is this correct? Since having a sphere as a distribution support is not really pathological, e.g., C.I. for Gaussian distribution, I think this is a serious problem. \n  \nBecause of this, \\textbf{their key example in Figure 6, the illustration of genuine adversarial accuracy (GAA) seems to be incorrect. } I checked the proof for Figure 6 in Appendix A. In the provided calculation of the GAA in Figure 6, they say that the Voronoi boundary is $VB(\\mathcal{X})=\\{0\\}.$ However, based on the their presented definition of Voronoi boundary, it seems to be incorrect. For example, let $x_1-=-1\\in\\bar{\\mathcal{X}}.$ Then, for any point $x'\\in(0,0.5),$ $\\|x'-x_1\\|=(x'+1)$. Define $x_2 =2x'+1$. Now we know that $x_2\\in\\bar{\\mathcal{X}}$ and $\\|x'-x_2\\|=(x'+1)$. Therefore, $(0,0.5)$ must be a subset of $VB(\\mathcal{X})$, and like wise $(-0.5,0)$ also must be. Therefore, at least $VB(\\mathcal{X})\\supset (-0.5,0.5).$ However, they caculate their results in Figure 6 by setting $VB(\\mathcal{X})=\\{0\\}.$ Therefore, the presented entire results in Figure 6 seem to contain errors.\n        \nLikewise, for this reason, the theoretical results seem dubious. \n\n2. Assuming somehow $VB(\\mathcal{X})$ is well defined, e.g., by a re-definition, the set \n$$S_{exact}(\\epsilon) = \\\\{x\\in\\bar{\\mathcal{X}}|\\exists x'\\in \\mathcal{X}_{\\epsilon}^c\\cap VB(\\mathcal{X})^c:\\|x'-x\\|=\\epsilon\\\\} $$  \nover which the expectation is taken seems not representing the data very well. The perturbations set is not defined or empty for so many data points. To see this, bet an $\\epsilon$-ball neighbor $B(\\mathcal{X},\\epsilon)=\\\\{x'|\\|x-x'\\|<\\epsilon, x\\in\\bar{\\mathcal{X}}\\\\}$ \n\nNow, your definition of $\\mathcal{X}_{\\epsilon}$ in page 5 is identical to \n\n$\\mathcal{X}_{\\epsilon} = VB(\\mathcal{X})^c\\cap B(\\mathcal{X},\\epsilon)$, \n\nwhich means $\\mathcal{X}_{\\epsilon}^c = VB(\\mathcal{X})\\cup B(\\mathcal{X},\\epsilon)^c$.\n\nTherefore, \n$$\\mathcal{X}_{\\epsilon}^c\\cap  VB(\\mathcal{X})^c = (VB(\\mathcal{X})\\cap VB(\\mathcal{X})^c)\\cup (B(\\mathcal{X},\\epsilon)^c\\cap VB(\\mathcal{X})^c) = B(\\mathcal{X},\\epsilon)^c\\cap VB(\\mathcal{X})^c\\subset B(\\mathcal{X},\\epsilon)^c$$\n \nNow, in the above definition of $S_{exact}(\\epsilon)$, $x'$  must be reached by $x\\in\\bar{\\mathcal{X}}$ by distance $\\epsilon$. In other words, any element in $S_{exact}(\\epsilon)$ must be able to reach to $B(\\mathcal{X},\\epsilon)^c$ by $\\epsilon$ distance. For example, if $\\mathcal{X}$ is again a unit sphere, then $S_{exact(\\epsilon)}$ is a subset of the surface of the sphere. Now, no matter how the classes are distributed \\emph{inside} the unit sphere, the genuine robust measure only consider the \\emph{surface} of the sphere to measure the robustness. \n\n\nThe second major concern is that the experiment section (section 4) seems not ready yet. It contains unsupported/self-contradicting arguments. Also, some additional information about the experiment conducted seems necessary.\n1. \\textit{This result gives us an insight that properly applied adversarial training(adversarial training (Goodfellow et al., 2014) with no conflicting regions originating from overlapping regions) will train models to mimic 1-NN classifiers as their training loss try to enforce them to make the same prediction as 1-NN classifiers}: The authors argue that this training's loss forces to predict on the training set as like 1-NN classifiers, which is optimal w.r.t. the genuine robust accuracy. The author may need to provide that when $\\epsilon$ is small, minimizing the standard adversarial loss is identical to maximize genuine robust accuracy. Otherwise, this argument does not make sense.\n2.  \\textit{If robustness to perturbations on the distance measure is not much related to generalization, it is possible that there exists a tradeoff between test accuracy and test adversarial robustness}: Why is that? This argument is confusing because so far the generalization is w.r.t. robustness, but all of sudden the authors are talking about tradeoff between natural accuracy and robustness. So far, you said that for a good distance metric, 1-NN classifiers will be robust also on the test dataset. Now, what are the missed sentences to get your conclusion on the trade-off?\n3. How do you define and measure proportions of agreements with 1-NN classifiers for Table 1 and 2? Do you test a point from the training set after adding some perturbations or not? If you add some perturbations, then how do you generate them?\n4. The result in Table 2 (among different predictions) is very different from Table 6 (on whole predictions). What is the definition of and difference between \"among different predictions\" and \"on whole predictions\"? Why does one show significantly different agreements, whereas the other show no almost no difference? \n5. Along the same line, the numbers in Table 2 are way larger than the numbers in Table 5. Why is that?\n6. In Table 1 and 2, I see that the agreement proportion values for non-adversarially trained models are different. For example, in table 2, 0.1529 for PGD-AT $\\epsilon=0.25$ and 0.1996 for PGD-AT $\\epsilon=1.0$. I guess that for PGD-AT $\\epsilon=0.25$ and $\\epsilon=1.0$, the non-adversarially trained model would be $\\epsilon=0$ for both models. Why do we see this difference? If they were not adversarially trained, and if they all have the same model architecture, these observed differences may challenge to the solidity of the experiment part. \n  \nOther concerns: \n1. The main contribution of this paper is unclear. First, the usefulness of this measure is unclear. We can not use this measure to measure the robustness of models as the authors do not provide a way to measure this genuine adversarial accuracy. They only compare the prediction of classifiers to that of 1-NN classifiers, which is by Theorem 2 optimal on the training set. Then, if it is difficult to measure genuine robust accuracy, then do you think the major usage of your measure is to show the lack of model capacity used for robust learning? Or, what is a main benefit of this proposed measure even in the absence of the specific algorithm to actually measure it?\n2. I do not see the theory and experimental results are coherent to their final conclusion. If I understand correctly, originally, the first experiment was intended to show the high agreement between 1-NN classifiers and adversarially robust models. By the argument of the authors, since the $\\epsilon$'s used for PGD-AT or TRADES are small enough based on Table 4, these trainings can be seen properly applied adversarial training. Then, the adversarially trained models on the training set should behave similarly to 1-NN classifiers. However, not as expected, in Table 1,2,5, and 6 the portion of agreement is at best about 0.6 for MNIST and 0.36 for CIFAR-10. Since those numbers are not close to 1, i.e., lower than as expected by Theorem 2, they are speculating these low numbers are due to the limited network capacities. However, in Conclusion, they say that \\textit{\" can mimic 1-NN classifiers. That was confirmed on analysis on CIFAR-10 data\"}, which is perplexing.  \n\nSuggestions and Questions:\n1. The definition of $VB(\\mathcal{X})$ could have been refined and some intuition about this definition could have been provided. Also, could you give a justification of your robust measure in my unit sphere example in 2?\n2. W.r.t. Table 4, I think it will be even more beneficial if the authors can provide the maximum of the minimum distance within the same class, across or within the training and test set. It will help to understand the robustness of 1-NN classifiers and the performance gab between 1-NN classifiers and other network based classifiers, either robust or not.\n3. The main body can be revised in a way that the major contribution is clear and extra information is located in a proper location. For example, too many new/necessary information is at the conclusion even in a parenthesis.\n4. In conclusion, for the sentence \\textit{\"That provides one possible factor ...why a tradeoff between test accuracy and test adversarial robustness might exist.\", }can you explain more about it? In your paper, I personally did not get any possible factor why a tradeoff happens.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Zw9565oGvxM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the question of adversarially robust classification---classifying inputs under worst-case norm-bounded corruptions. The authors argue that the standard notion of robust accuracy is inadequate for properly evaluating model performance and propose an alternative. Then, they show that for any fixed set of data points, the 1-Nearest-Neighbor classifier is the optimally robust classifier according to their proposed measure. Finally they measure empirically how similar existing robust classifiers are to the 1NN classifier.\n\nWhile the paper studies an interesting problem, the impact of its contributions is unclear:\n- **Inadequacy of robust accuracy.** The authors provide a number of toy examples that are unfortunately not convincing. In these examples, the notion of ground-truth label is undefined on most of the input space and the authors resort to arguments about an \"oracle classified\" and \"invariance-based adversarial examples\" which are not rigorously defined here. For instance, in the one dimensional examples, why is f2(x) not a good solution? It is perfectly accurate and robust up to eps=1. Similarly, in the sunset example, why is the top point classified as blue? Based on my understanding, in this dataset, the maximally robust classifier is exactly the max margin classifier and there is no trade-off between robustness and accuracy.\n- **Alternative notion of robust accuracy.** I was unable to understand the proposed definition at an intuitive level. How does it defer from standard accuracy? Why is it better? What does it mean to \"use a point more than once when calculating robustness\"?\n- **The 1NN classifier is maximally robust.** Since this statement if proved for a fixed set of datapoints, I do not understand its significance. Clearly, if we are given a set of points with their labels and we are asked to predict these labels *on the exact same set of points*, then using a 1NN classifier makes sense. But clearly, for many realistic machine learning problems (e.g., images) NN classifiers will inevitably perform poorly due to their inability to account for natural data invariances (e.g., image crops).\n- **Similarity of adv. trained models with the 1NN classifier.** I do not see the significance of this experiment. For instance, on CIFAR10, the 1NN classifier performs quite poorly so I'm not sure what this comparison is meant to convey.\n\nOverall, the paper need to significantly improve in focus, stating concrete and relevant research questions that its contributions are meant to answer.\n\nOther comments (not affecting score):\n- [This paper by Suggala et al.](https://arxiv.org/abs/1806.02924) also explores alternative notions of robust accuracy and are quite relevant.\n- There are several grammar issues  throughout the manuscript.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VZca9AXL6y2", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a novel metric for measuring adversarial accuracy of machine learning models, dubbed genuine adversarial accuracy. This is motivated by standard adversarial accuracy favouring in some instances classifiers with higher vulnerability to invariance-based adversarial examples.\n\nOne of my main reservation about this paper is the lack of significance. The genuine adversarial accuracy metric seems to be motivated by corner cases; the paper does not demonstrate the importance of this metric neither for practical evaluations of adversarial robustness nor for significant theoretical purposes.\n\nFurther observations:\n- In Definition 2: I don’t think it is common to define adversarial accuracy w.r.t. a specific loss function.\n- References are repeated numerous times, e.g. any mentioning of “adversarial training” is followed by the “(Goodfellow 2014)” reference, which is redundant and affects readability. \n- In 1.2.1: I don’t see why the oracle classifier will be f_3 or why it should even be uniquely determined.\n- In 1.3: The objective of adversarial training is not necessarily to improve accuracy on clean samples.\n- In 1.3.1: “is consists of” -> “consists of”\n- In Definition 3: What does it mean to “use exact perturbation norm”? The type setting could be improved by not putting equations under bullet points.\n- Avoiding “conflicts” of using points twice may not be required if those points have measure zero.\n- Theorem 1 immediately follows by definition - this is more of a proposition the proof of which is obvious.\n- Also Theorem 2 is obvious, and Section 3 consists of only one paragraph.\n- Section 4 is pretty vague and inconclusive. The argumentation relating adversarial training to generalisation of 1-KNN classifiers isn’t convincing.\n- The conclusions make several references to different parts of the Appendix which haven’t been discussed in the main body of the paper. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4QhOWHrMLcP", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper revisits previously known definitions of \"adversarial accuracy\" (and its complement: adversarial risk) which captures the accuracy (and risk) of learning models under adversarial perturbations of the test instances. The paper argues that the established (called standard) definition of adversarial accuracy has issues that need to be resolved, and then this work proposes a new definition (called genuine adversarial accuracy). The main issue they mention with previous definition is that they come at odds with accuracy. Their definition aims to fix this by giving an alternative way of defining accuracy. They then study the robustness of 1-NN under the newly proposed definition and claim that this algorithm is the most robust classifier according to this new definition. Proofs are differed to supplemental material.\n \n\n######################################################\n\nSummary of reasons for the score: \n\nUnfortunately, the paper’s treatment of the subject is not formal enough. The new definition also does not seem to be an improvement in any clear way. There is no given clear intuition for the new definition (which is quite complex to state) and what is exactly achieved. The theorem statements that are based on the definition are not formal either.\n \n \n##########################################################\n \nPros:\n \nUnderstanding the adversarial robustness (e.g., generalization of adversarially trained models) from a theoretic perspective is a very important and nontrivial problem. So, alternative (new) definitions that might allow us to understand the picture better are potentially highly valuable. This paper aims to improve the state of the art along this direction. \n \n#############################################################\n\nCons: \n\n \n1.\tUnfortunately, the paper does not clearly set objective goals to be achieved. The \"issues\" with previous definitions are not clearly discussed.\n\n2.\tThere are issues with the level of formality of the stated results, and the proposed definition is too complex to even read. No clear evidence is presented to justify the usefulness of the new definition in resolving challenges that previous definitions do not. A work aiming to settle definitional issues needs to be a lot more formal and precise.\n\n3.\tPrevious work has addressed some of the issues that the paper seems to be aiming to address. The papers [1,2] below (not cited) already point out a simple variation of the definition of adversarial risk under which there is no trade-off between accuracy and robustness. A simple way to prevent the definition of robustness to be at odds with accuracy is to require the adversarial sample (x^*) to be a misclassification. Also note that all these variants of definitions are equivalent to the main-stream definition (Def 1 in the paper), if one assumes that the underlying concept function (i.e., the ground truth) remains robust under the allowed amount of perturbation. So, in contexts such as image classification in which human is the ground truth and is already assumed to be robust to the amount of allowed noise/perturbation, the mainstream definition that is used has no issues. Issues arise when such definition are applied to a *different* context in which the ground truth might *not* be robust under the amount of allowed perturbation. \n\n[1] Suggala et al. \"Revisiting adversarial risk.\" aistats 2019.\n\n[2] Diochnos et al. \"Adversarial risk and robustness: General definitions and implications for the uniform distribution.\" NeurIPS 2018.\n \n#######################################################\n\nMain comments and questions:\n\nThe abstract states that:\n\"Based on this result, we suggest that using poor distance metrics might be one factor for the tradeoff between test accuracy and l_p norm-based test adversarial robustness.\"\nI am not sure how this conclusion was obtained. On a related note, I do not follow how Section 4 is expanding on this thesis.\n\nNote that l_p norm-based attacks are used since bounded l_p norms of perturbation does not seem to change human's judgement (there might be other perturbations that have this property too) so an *attack* under such limited perturbations is already an issue that needs to be addressed (but using such metrics for positive results could be questioned).\n\nIn problem setting page 1: why do you pick and fix the cross-entropy loss? It seems you want a general treatment of the definition of adversarial examples, and so other losses could be used as well?\n\nI think definition 2 is confusing two different notions: adversarial loss and surrogate losses used for training for computational reasons. \nOnce a candidate classifier f is trained, to know its risk/error under adversarial attacks, one shall *not* pick x* based on a loss such as cross-entropy loss. x* is simply a point in the Ball of allowed perturbations around x such that f(x*) is different from c(x) (assuming that c(x)=c(x*) – this means x* is also misclassified). A different question is how to train a model with minimum empirical adversarial loss. To do so, one needs to use computationally efficient approaches that might lead to using some surrogate loss instead of the 0/1 loss. \n\ntop of page 2:\n\"f2 and f3 are equally robust according to this measure. Thus, the maximum norm-based standard adversarial accuracy function cannot tell which classifier is better.\"\nI cannot follow the argument here. \n\nIn Def 3:\nConsider a case where X contains a ball of non-zero volume. Then, *every* point in R^d will belong to VB(X), as for every x' there will be two different points x1, x2 in X that have the same distance to x'. Then VB(X)^c will be empty, which makes your X_\\eps (allowed perturbation sets) to be empty. Is that so?\n\nIn your notation in the first bullet of page 5, what is the distribution over S_{exact(\\eps))? Note that stating the set alone is not enough to figure out what the expected value means, and since we are dealing with continuous settings the exact distribution is important to be state.\n\nTheorem 1 is not formally stated. \"adversarial accuracy only use each point only once\" is not a mathematically well-defined statement (especially in the continuous-domain regime). If you desire concrete properties that your definition implies, state those properties mathematically (e.g., if you are talking about a probability here, write it down formally).\n\nTheorem 2 is not formally stated. It is not clear what \"it is the almost everywhere unique1 classifier that satisfies\" means. What is the probability measure space here? You seem to say that \"with measure one\" in some probability space \"(1-NN) classifier maximizes genuine adversarial accuracy...\" if this is correct, the theorem needs to be restated differently.\n\n#########################################################################\n\nMore minor comments and typos:\n\nThe notation a_{std; max}(\\epsilon) is missing (and shall somehow denote) the function (f1 or f2) as well, as it depends on the function.\n\npage 3\n\"adversarial training try to\" -> \"tries to\"\n\npag3 4:\n\"dataset is consists\" -> remove \"is\"\n\"The other class (class B) is consist of\" -> consists of\n\npage 4: the points on the red circle are denoted as red, but you said the points \"points inside the circle classified as class A\". I guess you mean the points on and inside the circle are in class A?\n\n\n>> commented after the rebuttals:\nThanks for the answers. However, I think the paper still suffers from too many basic issues (still standing from the review). Main one is that it is not clear what the current definition is and what it achieves that previous definitions miss. There are informal texts, but they are not coherent formal and verifiable.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers new notions of adversarial accuracy and risk which are called "genuine" with an aim to fix issues with the existing definitions in the literature. A number of issues in the paper, including lack of motivation and intuition, and poor formalism were identified by the reviewers. The paper also fails to cite some of the previous literature that has identified similar issues. The authors have only responded to some of the questions raised by the reviewers. 
Decision: Reject