On the Power of Abstention and Data-Driven Decision Making for Adversarial Robustness
Authors: Nina Balcan
Avrim Blum
Dravyansh Sharma
Hongyang Zhang
Venue:  (2021)
Keywords: Adversarial Machine Learning
Learning Theory

Abstract: We formally define a feature-space attack where the adversary can perturb datapoints by arbitrary amounts but in restricted directions. By restricting the attack to a small random subspace, our model provides a clean abstraction for non-Lipschitz networks which map small input movements to large feature movements. We prove that classifiers with the ability to abstain are provably more powerful than those that cannot in this setting. Specifically, we show that no matter how well-behaved the natural data is, any classifier that cannot abstain will be defeated by such an adversary.  However, by allowing abstention, we give a parameterized algorithm with provably good performance against such an adversary when classes are reasonably well-separated in feature space and the dimension of the feature space is high. We further use a data-driven method to set our algorithm parameters to optimize over the accuracy vs. abstention trade-off with strong theoretical guarantees. Our theory has direct applications to the technique of contrastive learning, where we empirically demonstrate the ability of our algorithms to obtain high robust accuracy with only small amounts of abstention in both supervised and self-supervised settings. Our results provide a first formal abstention-based gap, and a first provable optimization for the induced trade-off in an adversarial defense setting.

Under review as a conference paper at ICLR 2021
ON THE POWER OF ABSTENTION AND DATA-DRIVEN DECISION MAKING FOR ADVERSARIAL ROBUSTNESS
Anonymous authors Paper under double-blind review
ABSTRACT
We formally define a feature-space space attack where the adversary can perturb data- points by arbitrary amounts but in restricted directions. By restricting the attack to a small random subspace, our model provides clean abstraction for non-Lipschitz networks which map small input movements to large feature movements. We prove that classifiers with the ability to abstain are provably more powerful than those that cannot in this setting. Specifically, we show that no matter how well-behaved the natural data is, any classifier that cannot abstain will be defeated by such an adversary. However, by allowing abstention, we give a parameterized algorithm with provably good performance against such an adversary when classes are reason- ably well-separated in feature space and the dimension of the feature space is high. We further use a data-driven method to set our algorithm parameters to optimize over the accuracy vs. abstention trade-off with strong theoretical guarantees. Our theory has direct applications to the technique of contrastive learning, where we empirically demonstrate the ability of our algorithms obtain high robust accuracy with only small amounts of abstention in both supervised and self-supervised set- tings. Our results provide first formal abstention based gap, and first provable optimization for the induced trade-off in an adversarial defense setting.
INTRODUCTION
substantial body of work has shown that deep networks can be highly susceptible to adversarial attacks, in which minor changes to the input lead to incorrect, even bizarre classifications Nguyen
let al., 2015 Moosavi-Dezzooll et al. 2016, Su et al. 2019 Brendel et al., 2018 Shamir et al. 2019).
Much of this work has considered l norm adversarial examples, but there has also been recent interest in exploring adversarial models beyond bounded f.-norm (Brown et al.) 2018 Engstrom et al. 2017: Gilmer et al.) 2018 Xiao et al.) 2018 Alaifari et al., 2019). What these results have in common that changes that either are imperceptible or should be irrelevant to the classification task can lead to drastically different network behavior.
One reason for this vulnerability to adversarial attack is the non-Lipschizzness property of typical neural networks: small but adversarial movements in the input space can often produce large perturbations in the feature space. In this work, consider the question of whether non-Lipschitz networks are intrinsically vulnerable, or if they could still be made robust to adversarial attack, in an abstract but (we believe) instructive adversarial model. In particular, suppose adversary, by making an imperceptible change to an input x, can cause its representation F(x) in feature space (the penultimate layer of the network) move by an arbitrary amount: will such adversary always win? Clearly if the adversary can modify F(x) (r) by an arbitrary amount in an arbitrary direction, then yes. But what if the adversary can modify F(x) by an arbitrary amount but only in a random direction (which it cannot control)? In this case, we show an interesting dichotomy: if the classifier must output classification on any input it given, then yes the adversary will still win, no matter how well-separated the classes are in feature space and no matter what decision surface the classifier uses. However, if the classifier is allowed to abstain, then it can defeat such an adversary so long as natural data of different classes are reasonably well-separated in feature space. Our results hold for generalizations of these models as well, such as adversaries that can modify feature representations in random -iw-enenniioal subspaces, directions that are not completely random. More broadly, our results provide a theoretical explanation for the importance of allowing abstaining, or selective classification, in the presence of adversarial attack.

---

Under review as a conference paper at ICLR 2021
Input
Feature
space
space
Figure 1: Illustration of a non-Lipschitz feature mapping using a deep network.
Apart from providing useful abstraction for non-Lipschitz feature embeddings, viewed as capturing an interesting class of real attacks. There are various global properties of an image, such brightness, contrast, or rotation angle whose change might be "perceptible but relevant" to classification tasks. Our model could also be viewed as an abstraction of attacks of that nature. Feature space attacks of other forms, where one can perturb abstract features denoting styles, including interpretable styles such as vivid colors and sharp outlines and uninterpretable ones, have also been empirically studied in (Xu et al. 2020 Ganeshan & Babu. 2019..
model may be
An interesting property of our model is that it is critical to be able to refuse to predict: any algorithm which always predicts class label thereeore without an ability abstain guaranteed to perform poorly. This provides first formal hardness result about abstention in adversarial defense, and also a first provable negative result feature-space attacks. We therefore allow the algorithm to output "don't t know" for some examples, which, as by-product of our algorithm, serves detection mechanism for adversarial examples. It also results in an interesting trade-off between robustness and accuracy: by controlling how frequently off against recall. We also provide results for how to provably optimize for such trade-off using data-driven algorithm. Our strong theoretical advances are backed by empirical evidence in the context of contrastive learning (He el al. 2020 Chen et al, 2020 Khosla et al. 2020
refuse to predict,
able trade (robust) precision
1.1
OUR CONTRIBUTIONS
Our work tackles the problem of defending against adversarial perturbations random feature subspace, and advances the theory and practice of robust machine learning in multiple ways.
We introduce formal model that captures feature-spact spacue attacks and the effect of non- Lipschitzness of deep networks which can magnify input perturbations.
We begin analysis with hardness result concerning defending against adversary without the option of "don't 't know". We show that all classifiers that partition the feature space into or more classes-the thus without an ability to abstain-are provably vulnerable to adversarial examples for at least one class of examples with nearly half probability.
We explore the power abstention option: variant of nearest-neighbor classifier with the ability to abstain is provably robust against adversarial attacks, even in the presence of outliers in the training data set. characterize the conditions under which the algorithm does not output "don't know" too often.
We leverage and extend dispersion techniques from data-driven decision making, and present novel data-driven method for learning data-specific optimal hyperparameters in our defense algorithms to simultaneously obtain high robust accuracy and low abstention rates. Unlike typical hyperparameter tuning, our approach provably converges to a global optimum.
Experimentally, we show that our proposed algorithm achieves certified adversarial robust- ness on representations learned by supervised and self-supervised contrastive learning, Our method significantly outperforms algorithms without the ability to abstain.
RELATED WORK
Adversarial robustness with abstention options. Classification with abstention option (a.k.a. selec- tive classification Geifmann & El- Yaniv
2017)) a relatively less explored direction in the adversarial machine learning. Hosseini et al. (2017) augmented the output class set with NULL label and trained the classifier to reject the adversarial examples by classifying them as NULL; Stutz et al. (020)) and Laidlaw & Feizi 2019) obtained robustness by rejecting low-confidence adversarial examples
2

---

Under review as a conference paper at ICLR 2021
according confidence thresholding predictions on the perturbations of adversarial examples. Another related line of research to our method is the detection of adversarial examples Grrosee et al.
2017
& Li 2017 Carlini & Wagner 2017 Ma et al. 2018 Meng & Chen 2017 Metzen et al.
2017
Bhagoji et al. 2018; Xu et al., 201 Hu et al.] 2019). However, theoretical understanding
behind the empirical success of adversarial defenses with abstention option remains elusive.
Data-driven decision making. Data-driven algorithm selection refers to choosing good algorithm from a parameterized family of algorithms for given data. It is known as "hyperparameter tuning" to machine learning practitioners and typically involves "grid search", "random search" (Bergstra
Bengio 2 or gradient-bant based search, with no guarantees of convergence to a global optimum. It was formally introduced to the theory of computing community by Gupta & Roughgarden (017)) as a learning paradigm, and was further extended in (Balcan et al. 2017). The key idea problem of identifying a good algorithm from data as a statistical learning problem. The technique has found useful application in providing provably better algorithms for several domains including clustering, mechanism design, and mixed integer programs, and providing guarantees like differential privacy and adaptive online learning (Balcan et al. 2018a by 2020). For learning in adversarial setting, we provide the first demonstration of the effectiveness of data-driven algorithm selection in a defense method optimize over the accuracy-abstenn trade-off with strong theoretical guarantees.
model the
3 PRELIMINARIES
Notation. We will use bold lower-case letters such as æ and y to represent vectors, lower-case letters such and represent scalars, and calligraphy capital letters such as X, y and 'D represent distributions. Specifically, we denote by a E X' the sample instance, and by y E y the label, where X C R and y' indicate the image and label spaces, respectively. Denote by F X R the feature embedding which maps an instance to a high-dimensional vector in the latent space F(X). It can be parameterized, e.g., by deep neural networks. We will frequently use IR "222 to represent an adversarial perturbation in the feature space. Denote by dist(..)) -) the distance between any two vectors in the image or feature space. Examples of distances include dist(æ1, x2) = [ - x22 x22l-tthe the one induced by vector norm. We use (ar, 7) to represent a neighborhood of æ:: {a' dist(x, x²) < r in the image or feature space. We will frequently denote by Dx the distribution of instances in the input space, by D Dx1y the distribution of instances in the input space conditioned on the class y, by Dr(a)) the distribution of features, and by D DF(x)y the distribution of features conditioned on the class y.
3.1 RANDOM FEATURE SUBSPACE THREAT MODEL
In principle, the adversarial example for given labeled data (x. is a data point x' that causes a classifier to output different label on x'' than the true label y. Probably one of the most popular adversarial examples is the norm- boundeddddd perturbation the input space. Despite a large literature devoted to defending against norm-bounde network as function mapping from input space to feature space (Zhang et al. 2019 Yang et al. 2020). it is typically not true that small perturbation in the input space necessarily implies small modification in the feature space. In this paper, we study a threat model where an adversary can modify the data by large amount in the feature space. Note that because this large modification in feature space is assumed to come from a small perturbation in input space, we always assume that the true correct label y is the same for x' as for x. Our model highlights the power of abstention in the adversarial learning: there is provable separation when we have and do not have an abstention option under our threat model.
adversary by improving the Lipschitzness of neural
Our threat model. In the setting of (robust) representation learning. we are given a set of training instances æI,..., 3m X. Let x: be an ni ni-dimensional test input for classification. The input is embedded into a high ng-dimensional feature space using a deep neural network F. We predict the class of by a prediction function F(x) which can potentially output "don't know". The adversary may corrupt F(x) such that the modified feature vector is restricted in a random ny -iyddmenniionl affine subspace denoted by S {F(x), while the perturbation magnitude might be arbitrarily large. The adversary is given access to everything including F, x, S and the true label of x. Throughout the paper, we will refer adversary and adversarial example this threat model.
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 ROBUSTCLASSIFIER(TT.
1: Input: A test feature F F()) (potentially an adversarial example), a set of training features F(x;)
and their labels yis E [m], threshold parameter т, separation parameter d.
2: Preprocessing: Delete training examples F F(x;) if min jem.)uu dist(F(a,,) F(æ,)) <
3: Output: A predicted label of F(x), or "don't 't know".
4: if mm) dist F(x), F(x:)) T then
5: Return Barg mingelm) dist( F F(m)))((m))
6: else
7: Return "don't 't know"
3.2 A META-ALGORITIM FOR INFERENCE-TIME ROBUSTNESS
Given a test data æ, let denote the shortest distance between F(x) and any training embedding F(x;) of different labels. Throughout the paper, we consider the prediction rule that we classify an unseen (and potentially adversarially modified) example with the class of its nearest training example provided that the distance between them is at most T: otherwise the algorithm outputs "don't know" (see Algorithm | and Figure 2 The adversary is able to corrupt F(x) by carefully- crafted perturbation along a random direction, i.c., F(x) + V. where v is an adversarial vector of arbitrary length in random ng ry-dimmnsional subspace of "R22, The parameter trades the success rate off against the abstention rate; when 7 -> oc, our algorithm equivalent to the nearest-neighhor algorithm. We also preprocess remove outliers and points too close them.
F(x)
F(x)
2 r
F(x) +
Figure 2: Adversarial misclassification for nearest-neighhor predictor.
NEGATIVE RESULTS WITHOUT AN ABILITY TO ABSTAIN
Several negative results are known for defending against adversarial examples beyond norm-bounded settings. For example, Shamir et al. (2019) provably show existence of targeted adversarial examples with small hamming distance in the input space their clean examples. For feature space attacks, several empirical negative results are known (Xu et al. 2020 Ganeshan & Babu (019). We present hardness result concerning defenses without an ability to abstain, and prove that such defenses are inevitably doomed against our feature-space attacks.
Theorem 4.1. For any classifier that partitions R== into two or more classes, any data distribution D, any 5 0 and any feature embedding F, there must exist at least one class y", such that for at least a 1 - 8 probubility mass of examples x: from class y" (i.e., æ is drawn from Dx X'y" ), for random unit-length vector v, with probability at least 1/2 - 8 for some 8g > 0, F(x) + dgv is not labeled y" by the classifier. In other words, there must be at least class y such that for at least 1 probability mass of points x of class y" , the adversary wins with probability at least 1/2 5.
Proof. Without loss of generality, we assume that the feature embedding F is an identity mapping. Define ra to be a radius such that for every class at least a 1 - probability mass of examples æ of class y lie within distance r3g of the origin. Let R rs n2// 8. R is defined to be large enough such at least 1 fraction of the volume
that if we take a ball of radius R and move it by a distance of the new ball is inside the intersection with the old ball. Now, let be the ball of radius R centered at the origin. Let vol(B) denote the volume of B and let vBl) denote the volume of the subset of B that is assigned label by the classifier. Let y be any label such that voly- (B) (B)/vol(B) < 1/2. Such do not have the option to output "don't 't know". Now by the definition
class y" exists because of yy," point z picked uniformly at random from B has probability at least 1/2 of being classified differently from y". This implies that, by the definition of Rt if is within distance ra of the origin,
4

---

Under review as a conference paper at ICLR 2021
then point Zy that is picked uniformly at random in the ball BN of radius R centered has probability at least 1/2 - of being classified differently from y" This immediately implies that choose random unit-length vector then with probability at least 1/2 - 8, there exists ón such that a + ōg v is classified differently from , since we can think of choosing v by first sampling Zy from B, and then defining
(Zg / 2zz x æ=|2- So, the theorem follows from the fact that, by the definition of rs, at least 1 probability mass of examples æ from class y" are within distance rs of the origin.
We remark that our lower bound applies to any classifier and exploits the fact that a classifier without abstention must label the entire feature space. For a simple linear decision boundary (center of Figure D a perturbation any direction (except parallel to the boundary) can cross the boundary with appropriate magnitude. The left and right figures show that if we try 'bend' the decision boundary to 'protect' one of the classes, the other class is still vulnerable. Our argument formalizes and generalizes this intuition, and shows that there must be at least one vulnerable class irrespective of how you may try to shape the class boundaries, where the adversary succeeds in a large fraction of directions.
D
ogo
Figure 3: A simple example to illustrate Theorem 4.1
Theorem 4.1 implies that all classifiers that partitions _2 into two more classes-thus without an ability to abstain are vulnerable to adversarial examples for at least one class of data with nearly half probability. Despite much effort has been devoted empirically investigating the power of "don't 't know" in the adversarial robustness, theoretical understanding behind the empirical success of these methods remains elusive. To the best of our knowledge, our work is the first result that provably demonstrates the power of "don't know" in the algorithmic design of adversarially robust classifiers.
POSITIVE RESULTS WITH AN ABILITY TO ABSTAIN
Theorem 4.1 gives hardness result of robust classification without abtention. this section, we explore the power of abstaining and show classifiers with an ability to abstain are provably robust.
Given a test instance æ Dx, recall that denotes the shortest distance between F(x) RR and any training embedding F(x;)) E IR22 with a different label. The adversary is allowed to corrupt F(x:) with an arbitrarily large perturbation in uniform-distributer subspace of dimension ni- Consider the prediction rule that classify the unseen example F(x) I with the class of its nearest training example provided that the distance between them is at most T; otherwise the algorithm outputs "don't t know" (see Algorithm when
0). Denote by E (f) := Eg-s1 s e S F(x) S R s.t. f(c) + y and f(c) does not abstain) } the robust error of a given classifier f for classifying instance Our analysis leads to the following positive results this algorithm.
Theorem 5.1. Let Dx be test instance, be the number of training examples and be the shortest distance between F(x) and F(x;)) where x; is a training point from a different class. Suppose
(r
na
The robust error of Algorithm / Endy (ROBUSTCLASSSFFEER 0)),
n2
22 ng
at most m
mcp
R2-ng where and co are absolute constants.
Proof Sketch. We begin analysis with the case of ny 1. Suppose have training example x' of another class, and suppose F(x) and F(x') are at distance in the feature space. Because o (D), the probability that the adversary move F(x:) to within distance of F(x') should
5

---

Under review as a conference paper at ICLR 2021
be roughly the ratio of the surface area of sphere of radius to the surface area of sphere of radius D, which at most (O (t)) ( (-)) The analysis for the general case of ng follows from a pealing argument: note that the random subspace in which the adversary vector is restricted to lie can be constructed by first sampling a vector V1 uniformly at random from a unit sphere in the ambient space R centered at O; fixing V1, then sample vector V2 uniformly at random from a unit sphere in the null space of span (v1); ;; we repeat this procedure ng times and let span(v1); span V1, V2,-..g V be the desired adversarial subspace. For each step of construction, we apply the same argument that of nı 1 with D 52
('v
na-i
by high probability, if project A2
F(x:) and F F(x') to random subspace of dimension n2 i. Finally, a union bound over training points completes the proof.
Trade-off between success probability and abstention rate. Theorem 5.1 captures the trade-off between the success probability of an algorithm and the abstention rate: a smaller value of T increases the success probability of the algorithm, while it also encourages Algorithm T to output "don't 't know" more often. A related line of research to this observation is the trade-off between robustness and accuracy: Zhang al. (2019): Tsipras al. (2019) showed that there might be no predictor in the hypothesis class that has low natural and robust errors; even such a predictor exists for the well-separated data (Yang et al., 2020), Raghunathan
al. (2020) showed that the natural error could increase by adversarial training if we only have finite number of data. To connect the two trade-offs,, we note that a high success probability of KOBUSTCLASSIFEES
0) Algorithm tends to avoid the algorithm from predicting wrong labels for ad adversarial examples, while the associated high abstention rate encourages the algorithm to output "don't 't know" even for natural examples, thus leading to a trivial non-accurate classifier.
5.1 A MORE GENERAL ADVERSARY WITH BOUNDED DENSITY
We extend our results to a more general class of adversaries, which have a bounded distribution over the space of linear subspaces of a fixed dimension n3 and the adversary can perturb a test feature vector arbitrarily in the sampled adversarial subspace.
Theorem 5.2. Consider the setting of Theorem 5.7 with an adversury having rs-bounded distri- bution over the space of linear subspaces of a fixed dimension ny for perturbing the test point. If
E (r, r) denotes the bound error rate in Theorem 5.1 for ROBUSTCLASSIFEER
0) in Algorithm then the error bound of the same algorithm against the k-bounded adversary is ((K((T,r)
5.2 OUTLIER REMOVAL AND IMPROVED UPPER BOUND
The upper bounds above assume that the data is well cell-separated in the feature space. For noisy data and good-but-not not-perfeet embeddings, the condition may not hold. In Theorem (..oremE.TTii (in Appendix E show that obtain almost the same upper bound on failure probability under weaker assumptions by exploiting the noise removal threshold σ.
5.3 CONTROLLING ABSTENTION RATE ON NATURAL DATA
We show that we can control the frequency of outputting "don't know", when the data nicely distributed according to the following generative assumption. Intuitively, it says that for every label class one can cover most of the distribution of the class with (potentially overlapping) balls of fixed radius, each having a small lower bound on the density contained. This holds for well-clustered datasets (as is typical for feature data) for sufficiently large radius.
Assumption 1. We assume that at least 1 - ò fraction of mass of the marginal distribution Dr(X) over T2 can be covered by N balls B,, B2, Bn of radius 7/2 and of mass PTD [Bx] 2
Co n2 log m + log 1/) where Co > 0 is absolute constant and 6, (0,
AN
Our analysis leads to the following guarantee on the abstention rate. Theorem 5.3. Suppose that F( (..,, F(xm) are m training instances i.i.d. sampled from marginal distribution DF(zy. Under Assumption with probability at least 1 -3/4 over the sampling, we have Pr(up, BB (a:)) 7)) 2 1 8.

---

Under review as a conference paper at ICLR 2021
Theorem 5.3 implies that when Pr[Bx] 2 8
N and Q N log 3 with probability least 1 3/4 over the sampling, we have Pr(U ((F()) 2 1-6. Therefore, with high probability, the algorithm will output "don't t know" only for an ò fraction of natural data.
LEARNING DATA-SPECIFIC OPTIMAL THRESHOLDD
Given an embedding function F and classifier fr which outputs either a predicted class if the nearest neighbor is within distance 7 of a test point or abstains from predicting, we want to evaluate the performance of f- on test set T against an adversary which can perturb test feature vector in a random subspace S ~ S. To this end, we define Eadv(T) == Es . L(s, ET 1 E S+ F(x) 2 s.t. f(e) # y and (c) does not abstain) as the robust error the test set T, and (T) == ग. ET (F())) abstains} as the abstention rate on the natural data. Eadv(T) and (T) monotonic in The robust error (T) is optimal at T O, while abstain from prediction all the time (i.e., (T) = 1). A simple approach is to fix an upper limit d' on (T), which corresponds the maximum abstention rate on natural data under it is straightforward to search for the optimal -* such that D (T") x d by using nearest neighbor distances of test points. For T" we have a higher abstention rate, and when T > I" we have higher robust eπror rate. A potential problem with this approach is that Pasc is non- non-Lipschitz, so small variation in can possibly make the abstention rate significantly higher than d'.
budget. Then
An alternative objective which captures the trade-off between abstention rate and accuracy is defined as (T) : Eadv + cDaat (T), where is positive constant. If, for example, we are willing to take one percent increase of the abstention rate for a two percent drop in the error rate, we could set e to be 3. We can optimize g(T) a data-driven fashion and obtain theoretical guarantee on the convergence to a global optimum. In the following, we consider the case where the test examples appear in an online fashion in small batches of size b, and we set the threshold T adaptively by a low-regret algorithm. We note in Corollary 6.3 using online-to-ban to-bachh conversion, that our results imply uniform convergence bound for objective g(T) in the supervised setting. Details of proofs in this section can be found in Appendix H
The significance data-driven design in this setting is underlined by the following two observations. Firstly, noted above, optimization for r is difficult due to the non-Lipschitzness nature of Daat (7) and the intractability of characterizing the objective function g(T) exactly due to ( Secondly, the optimal value of can be complex function of the data geometry and sampling rate. We illustrate this by exact computation of optimal r for a simple intuitive setting: consider a binary classification problem where the features lie uniformly on two one-dimensional manifolds embedded in wwo-dimensions (i.e., n22 = 2, see Figure 4. Assume that the adversary perturbs in uniformly random direction (n3 = 1). For this setting, in Appendix we show that
Theorem 6.1. Let T* = arg maX+ 9(T) and / 2ser For the setting considered above, if we further assume D = o(r) and m = w (log 3). then there is a unique value of T" in [0, D D/2).
D
Furthermore, we have T" = θ log(8m)) ) if m > 3: otherwise, ===
D
D
r
Class
Class B
Figure 4: A simple intuitive example where we compute the optimal value of the abstention threshold exactly. Classes A and B are both distributed uniformly on one-dimensional segments of length D, embedded collinear and at distance in R
The remaining section summarizes our main theoretical results.
Theorem 6.2. Assume T is (min(m-1/ng (nnnt and the data distribution is contimuous, k-bounded,
positive and has bounded partial derivatives. T set using a continuous version of the multiplicative updates algorithm (Algorithm)) 2 in Appendix H Balcan el al. (2018a)), ) then with probability at least
<RRTmb where R is a bound 1 - 5, the expected regret in T rounds is bounded by O (V n22 log Spng-my
7

---

Under review as a conference paper at ICLR 2021
on the largest distance between any two training points, b is the batch size, and is the smallest distance between points of different labels.
Corollary 6.3. Suppose we run the online algorithm of Theorem 6.2 on a validation set of size T, and use randomized threshold i on the test set drawn from a uniform distribution over the thresholds Ti....;TT TT used online learning. If the threshold which maximizes g(T) T", then with probubility <RTTm 8r
greater than 1 1-6 6. we have [Elgff)--g(1) - S (V log
Remark 1. The results can be generalized to a bounded density adversary (Corollary
11.3
Remark 2. The above analysis can be extended the problem of optimizing over by formulating the objective as function of two parameters, g(T, := Endv (T, o) cDuat o) within a range a E [r, s]. For fixed т, both Endv(T, (T, a) and D o) are piece-wise constant and monotonic. The proof of Lipschitaness of the pieces can be adapted easily to the case of 2 (Lemma [1.2). Discontinuities in (T. and Dust (T,') can be bounded using the upper bound 8 for a (Lemma H.4y. Finally, the number of discontinuities in g(T, in ball of radius w be upper bounded by a product of the number of discontinuities in g(T, and g(, σ) in intervals of width w.
7 EXPERIMENTS ON CONTRASTIVE LEARNING
Theorem 5. sheds light on algorithmic designs robust learning of feature embedding F. In order to preserve robustness against adversarial examples regarding a given test point æ, in the feature space the theorem suggests minimizing T- T-the closest distance between F(x) and any training feature F(x;) of the same label, and maximizing r r-the closest distance between F(z) and any training feature F(x;) of different labels. This is conceptually consistent with the spirit of the nearest-neighbor algorithm, a.k.a. contrastive learning when we replace the max operator with the softmax operator for differentiable training.
[((e)) Flee)1
Σ Eje(m))
Σ log min
771
Eke(m],yy [I(ee) 11
where T >> 0 is the temperature parameter. Loss is also known as the soft noft-nearest-neighbor loss in the context of supervised learning (Frosst et al. 2019), or the InfoNCE loss in the setting of self-supervised learning (He et al. 2020
7.1 CERTIFIED ADVERSARIAL ROBUSTNESS AGAINST EXACT COMPUTATION OF ATTACKS
We verify the robustness of Algorithm | when the representations are learned by contrastive learning. Given a embedding function F and a classifier f which outputs either a predicted class or abstains from predicting, recall that we define the natural and robust errors, respectively, as Enat (f) == ((a.y)=Dl(f((()
+ y and (F(()) does not abstain), and Eadv := E(a.,)) 1 e S F(x) C R2 s.t. f(e) + y and f(c) does not abstain]. where S ~ S is random adversarial [F abstains) } is the abstention rate on the natural examples. Note that the robust error is always at least as large as the natural error.
subspace of "R" with dimension n2. D (f) :=
Self-supervised contrastive learning setup. Our experimental setup follows that of SimCLR (Chen al. 2020). We use the ResNet- 18 architecture (He et al. 2016) for representation learning with a two- loyer projection head of width 128. The dimension of the representations is 512. We set batch size 512, temperature T 0.5, and initial learning rate 0.5 which followed by cosine learning rate decay. We sequentially apply four simple augmentations: random cropping followed by resize back to the original size, random flipping, random color distortions, and randomly converting image to grayscale with probability of 0.2. In the linear evaluation protocol, set batch size 512 and learning rate 1.0 to learn a linear classifier in the feature space by empirical risk minimization.
Supervised contrastive learning setup. Our experimental setup follows that of Khosla et al. (2020). We use the ResNet-18 18 architecture for representation learning with a two-layer projection head of width 128. The dimension of the representations is 512. We set batch size 512. temperature T 0.1, and initial learning rate 0.5 which is followed by cosine learning rate decay. We sequentially apply four simple augmentations: random cropping followed by resize back to the original size, random
8

---

Under review as a conference paper at ICLR 2021
Table 1: Natural error Eas and robust error Egdy the CIFAR-10 dataset when ng 1 and the 512-dimensional representations are learned by contrastive learning, where Dnat represents the fraction of each algorithm's 's output of "don't 't know" on the natural data. We report values for as they tend to give good abstention-error trade-off w.r.t.
Contrastive
Linear Protocol
Ours (T 3.0)
Ours (T 2.0)
Enst
Eadv
Enst
Eddy
D
Dust
East
Eddy
D Dast
Self-supervised
8.9%
100.0%
15,4%
40.7%
2.2%
14.3%
26.2%
28.7%
(a = 0)
Supervised
5.6%
100.0%
5.7%
60.5%
0.0%
5.7%
33.4%
0.0%
Self-supervised
8.9%
100.0%
7.2%
9.4%
12.9%
10.0%
17.7%
29.9%
(a 0.9r)
Supervised
5.6%
100.0%
6.2%
18.9%
0.0%
5.6%
22.0%
0.1%
Self-supervised
8.9%
100.0%
1.1%
1.2%
33.4%
2.1%
3.1%
49.9%
(a = r)
Supervised 5.6%
100.0%
1.9%
2.8%
10.6%
4.1%
4.8%
3.3%
flipping, random color distortions, and randomly converting image to grayscale with probability of 0.2. In the linear evaluation protocol, we set batch size 512 and learning rate 5.0 to learn a linear classifier in the feature space by empirical risk minimization.
In both self-supervised and supervised setups, we compare the robustness of the linear protocol with that of our defense protocol in Algorithm Uundr exact computation of adversarial examples using a convex optimization program in dimensions and m constraints. Algorithm in the appendix provides an efficient implementation of the attack.
Experimental results. We summarize our results in Table Comparing with a linear protocol, our algorithms have much lower robust error. Note that even if abstention is added based distance from the linear boundary, sufficiently large perturbations will ensure the adversary can always succeed. For an approximate adversary which be efficiently implemented for large na, Appendix
7.2 ROBUSTNESS-ASSTENTON TRADE-OFT
The threshold parameter captures the trade-off between the robust accuracy Aadv := Eadv and the abstention rate 'nnat on the natural data. We report both metrics for different values of r for supervised and self-supervised constrastive learning. The supervised setting enjoys higher adversarial accuracy and a smaller abstention rate for fixed r's due to the use extra label information. We plot Asdv against Duat for Algorithm D as hyperparameters vary. For small т. both accuracy and abstention rate approach 1.0. As the threshold increases, the abstention rate decreases rapidly and our algorithm enjoys good accuracy even with small abstention rates. For - ao (i.e. the nearest neighbor search), the abstention rate on the natural data Duat is 0% but the robust accuracy is also roughly 0%. Increasing (for small σ) gives us higher robust accuracy the same abstention rate. Too large may also lead to degraded performance.
Supervised
Self-supervised
robust accuracy
accuracy
a 2.0
d
a 5.0
=
100
abstention on natural data
abstention on natural data
Figure 5: Adversarial accuracy (i.e., rate of adversary failure) vs. abstention rate as threshold varies for n3 and different outlier removal thresholds a.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Rima Alaifari, Giovanni S Alberti, and Tandri Gauksson. ADef: an iterative algorithm to construct adversarial deformations. In International Conference on Learning Representations, 2019.
Philip Bachman, Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. In Advances in Neural Information Processing Systems, pp. 15535-15545, 2019.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning -thhorrticcht foundations of algorithm configuration for combinatorial partitioning problems. In Annual Confer- on Learning Theory, pp. 213-274, 2017.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In Annual Symposium Foundations of Computer Science, pp. 603-614. IEEE, 2018a.
Maria-Floring Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In ACM Conference on Economics and Computation, pp- 173-174, 2018b.
Maria-Florina Balcan, Travis Dick, and Dravyansh Sharma. Learning piecewise Lipschitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics, pp. 3567-3577, 2020.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. The Journal of Machine Learning Research, 13(1):281-305 2012.
Arjun Nitin Bhagoji, Daniel Cullina, Chawin Sitawarin, and Prateek Mittal. Enhancing robustness of machine learning systems via data transformations. In Annual Conference on Information Sciences and Systems, pp. 1-5, 2018.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify too robustness for nigh-dimensiooal images. Journal of Machine Learning Research, 2020.
Wieland Brendel, Jonas Rauber, Alexey Kurakin, Nicolas Papernot, Behar Veliqi, Marcel Salathé, Sharada P Mohanty, and Matthias Bethge. Adversarial vision challenge. arXiv preprint arXiv:1808.01977 2018
Tom B Brown, Nicholas Carlini, Chiyuan Zhang, Catherine Olsson, Paul Christiano, and Ian Good- fellow. Unrestricted adversarial examples. arXiv preprint 1rX9v:1809.044 2018.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten
detection methods. In ACM Workshop Artificial Intelligence and Security, pp. 3-14, 2017.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for the cluster tree. In Advances in Neural Information Processing Systems, pp. 343-333333 143-351,77 2010.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and translation suffice: Fooling CNNs with simple transformations. arXiv preprint arXiv:1712.02779, 2017.
Dafydd Evans, Antonia J Jones, and Wolfgang M Schmidt. Asymptotic moments of near-neighhour distance distributions. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 458(2028) 2002.
Nicholas Frosst, Nicolas Papernot, and Geoffrey Hinton. Analyzing and improving representations with the soft nearest neighbor loss. In International Conference on Machine Learning, 2019.
10

---

Under review as a conference paper at ICLR 2021
Aditya Ganeshan and R Venkatesh Babu. FDA: Feature disruptive attack. In IEEE International Conference on Computer Vision, pp. 8069-8079, 2019.
Yonatan Geifman and Ran El- El-iv,,v, Selective classification for deep neural networks. In Advances in neural information processing systems, pp. 4878 4887, 2017.
Justin Gilmer, Ryan P Adams, lan Goodfellow, David Andersen, and George E Dahl. Motivating the rules of the game for adversarial example research. arXiv preprint 1rXiv:1807.06732 2018.
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick McDaniel. On the (statistical) detection of adversarial examples. arXiv preprint arXiv:/702..06280 2017.
Rishi Gupta and Tim Roughgarden. A PAC approach to application-specifie algorithm selection.
SIAM Journal on Computing, 46(3);992-1017, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In IEEE Conference on Computer Vision and Puttern Recognition, pp.
2020.
Olivier J Hénaff, Aravind Srinivas, Jeffrey De Fauw, Ali Razavi, Carl Doersch, SM Eslami, and Aaron van den Oord. Data-efficient image recognition with contrastive predictive coding, arXiv preprint ar 1tt5::99000022.. 2019.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 180.0680000660, 2018.
Hossein Hosseini, Yize Chen, Sreeram Kannan, Baosen Zhang, and Radha Poovendran. Block- ing transferability of adversarial examples black-box learning systems. arXiv preprint arXiv: 00000.04438.... 2017.
Shengyuan Hu, Tao Yu, Chuan Guo, Wei-Lun Chao, and Kilian Weinberger. A new defense against adversarial images: Turning a weakness into a strength. In Advances in Neural Information Processing Systems, pp. 1635-1646, 2019.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sama,, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. arXiv preprint arXiv:2004. / 1362, 2020.
Cassidy Laidlaw and Soheil Feizi. Playing it safe: Adversarial robustness with an abstain option. arXiv preprint 1911. 2019.
Xin Li and Fuxin Li. Adversarial examples detection in deep networks with convolutional filter statistics. In IEEE International Conference Computer Vision, pp. 5764-5772, 2017.
Xingjun Ma, Bo Li, Yisen Wang. Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song. Michael E Houle, and James Bailey, Characterizing adversarial subspaces using local intrinsic dimensionality. In International Conference on Learning Representations, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Dongyu Meng and Hao Chen. MagNet: two- two-pronged defense against adversarial examples. In ACM SIGSAC conference on computer and communications security, pp. 135-147, 2017.
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. In International Conference on Learning Representations, 2017.
Seyed- Seyed-Mohsen accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582 2016.
Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and

---

Under review as a conference paper at ICLR 2021
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 427-436, 2015.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprini arXiv:
2018.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. In International Conference on Machine Learning, 2020.
Adi Shamir, Itay Safran, Eyal Ronen, and Orr Dunkelman. A simple explanation for the existence of adversarial examples with small hamming distance. arXiv preprint
2019.
David Stutz, Matthias Hein, and Bernt Schiele. Confidence-calibrated adversarial training: Generaliz- ing to unseen attacks. In International Conference on Machine Learning, 2020.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 23(5):828-84) 841, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint arXiv:1312.6199, 2013.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding, In European Conference on Computer Vision, 2019.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Ro- bustness may be at odds with accuracy. In International Conference on Learning Representations, 2019.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via man-aarametric instance discrimination. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 3733-3742, 2018.
Chaowei Xiao, Jun- Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. In International Conference on Learning Representations, 2018.
Qiuling Xu, Guanhong Tao, Siyuan Cheng, Lin Tan, and Xiangyu Zhang. Towards feature space adversarial attack. arXiv preprint arXiv:2004. /2385, 2020.
Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. In Network and Distributed Systems Security Symposium, 2017.
Yao- Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. Adversarial robustness through local Lipschitzness. In Advances in neural information processing systems, 2020.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference Machine Learning, 2019.
Chengxu Zhuang, Alex Lin Zhai, and Daniel Yamins. Local aggregation for unsupervised learning of visual embeddings. In IEEE International Conference on Computer Vision pp. 6002-6012, 2019.
12


Reviews:
[{"review_id": "sDaqzNKpqFd", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Summary:\n\nThis paper studies, through a provable approach, whether abstaining (i.e., refusing to answer) can be beneficial for achieving small adversarial/robust error in settings where the input is potentially adversarially perturbed. The paper proves a separation between the power of models with and without abstain. In particular, it is shown that for a certain adversarial model (more about this below) when we force the model to answer without an abstain option, it will have high adversarial error, but when abstain is allowed, it can have small adversarial error as well as small abstention rate in certain settings. The paper then studies algorithms for robust contrastive learning in which they map the inputs into high-dimensional spaces and then aim to classify them using an abstain-enabled model based on 1-NN. The paper studies ways to adjust the parameters of the model as the data comes in an online fashion (divided into batches). They show how to achieve sublinear regret in such settings. They then compare linear classifiers with their own (1-NN style) classifiers and show advantages in robustness with such models when abstaining is allowed.\n\nPros: \n\nNot many previous works have studied the role of abstention in adversarial attacks (aka adversarial examples / evasion attacks). This work is the first to aim for a provable separation. This is a very natural and potentially impactful direction. The ideas for the algorithm design (through a data driven approach) could lead to useful methods that have practical values.\n\nCons:\n\nI think the theoretical separation is not that meaningful due to two issues:\n1. The robustness is defined for an un-natural perturbation model: it is a mixture of random and adversarial (i.e., the perturbations are allowed to be in a *randomly selected* subspace) but that is not the main issue. The main issue is that the amount of perturbation in the subspace is *unbounded*. This means the adversary can basically perturb the point to an arbitrarily far point where the *ground truth* also changes. Therefore, it is not cleat at all if the perturbed point would indeed be mis-classified or not, which seems to be the minimum requirement to call something adversarial example. Here I want to contrast the noise model with, say, ell_p-based noise model that is extensively studied in the literature to clarify the issue. The idea there is that, e.g. in the case of images, bounded ell_p perturbation preserves the ground truth (in that case human’s judgement). So, an attack that finds images with small ell_p distance with a different classified label would be misclassified. Here, nothing like that could be said as perturbations are arbitrarily long. \n2. To see (a different but related) issue with the definition used for robust error assume a function f(.) completely learns the concept correctly and have zero error. Then on the one hand, such model should not be able to have an adversarial example, because any perturbation would be *correctly* answered (i.e., imagine a change in a cat image to modify it into a dog picture and when the model says it is a dog, we count this as error). However, the definition used in this paper would still allow to prove *unconditional* adversarial error for the model. Note that previous works (e.g., the cited work of Madry et al.'18) are (sometimes implicitly) defined for a setting that the perturbation cannot change the ground truth (e.g., bounded perturbation of images do not change human judgement, so if the label changes it would be misclassified) but here the noise allows arbitrarily far perturbations.\n\n-  It seems the experiments compare the new method (with possible abstention) with a linear classifier that is not designed to be robust.\nI think a fairer way to show the advantage of abstain is to show that your method (with abstain) can beat another previous method that was designed to be robust (e.g., using traditional adversarial training). That would show a real jump in what we can do with abstention.\n\nDue to the above reasons, I think the theoretical and the experimental contributions can be interpreted in a limited way, and hence I am more inclined to recommend rejection.\n\nMain comments:\n\nIn Algorithm 1: line 2: do you do this in some order? e.g., if two points are at distance less than sigma, you remove one of them or both of them?\n\nDiscussions after Theorem 5.1 somehow interpret it as showing some form of (inherent) trade-off between success probability and abstention rate on *normal* (not adversarial) inputs. But that does not seem to be necessarily the case. For example, going back to the case of images. Note that the input distribution (e.g., images in CIFAR-10) keep their concept label even after perturbation (e.g., human judgement). Now, one can either ask a robust model to output a label *even when images are perturbed* or be allowed to abstain when a perturbed image is given. In the latter case, a model can actually have 100% accuracy on the normal inputs, while it might have a lot of abstain on adversarially perturbed points. The disparity between my example and the message of Theorem 5.1 seems to be either stemming from the fact that you allow arbitrarily long perturbations (that will eventually change the label) or that 1-NN based approaches are not sufficiently powerful here. \n\nAssumption 1 page 5: \n\"We assume that at least 1 − delta fraction of mass of the marginal distribution D_{F(X)|y} over...\"\nIs this for every y?\nAlso, can you discuss whether Assumption 1 typically correct on real data?\n\nIn your experiments (reported in Table 1 (page 8)) how much the numbers change if you aim to get an adversarially perturbed point misclassified (by further restricting what constitutes as a legitimate adversarial example). My objection above to the theoretical formulation and proofs does not prevent you from (potentially) showing a separation in these experiments by really forcing the adversarial examples to be misclassified.\n\nIs your approximate adversary provably approximating the robust error?\n\n###############################\n\nFurther comments (and typos):\n\nThe label y appears (twice) in the proof of page 4 as non-math (missing $..$).\n\nD_nat does not seem to be the best choice to represent the abstention rate on normal data (at least it is hard to guess it based on the notation).\n\n\n***** post rebuttal comment *****\n\nThanks for sharing the response. Unfortunately, the very basic issue with the definition used in this paper, and its implications to practice, remains unsolved.\n\nTo clarify the definition, you just need to focus on the following simple example: what if the model has zero risk/error?  If you perturb a point, it would still be correctly classified. Yet, they still show that adversarial examples are inevitable even in this setting. This already shows something is fundamentally wrong with the definition used.\n\nYour response is that the attacker/adversary will not get to change the label, but only the features. But please note: the adversary *is not allowed* to choose the label. The adversary picks the features, and it is up to the model to correctly classify it or not. If an attacker changes the picture of a cat to to a picture of a dog, the neural net (or any other model) should call this dog (and if does still calls it cat it would be a a mistake not the other way around). The ground truth (i.e., the concept function) determines what is correct and what is not. \n\nThe above issue is not imaginary, it has real affect on the experiments, and as I said, it is important to report in the experiments whether or not they attacks lead to *actual misclassification*.\n\nI hope these comments will help improving the paper, since as I said, the topic of this paper is a very important one, and so exactly because of this, it is important to have the basics right.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TLg9eELBaXd", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper proves some fundamental facts about classifiers that can't abstain (provide a non-classification) and their robustness to adversarial perturbations. In Sec. 4, they provide a result that such classifiers are always vulnerable to adversarial perturbations in a technical sense. In particular, there will always be a class in which most training examples can be randomly perturbed in a way that an incorrect label will result nearly half the time. In Sec 5, they propose a modified nearest-neighbor classification algorithm, with two parameters that control abstention and \"noise removal\". They provide upper bounds on error in a random subspace attack scheme, and refine/loosen these results in several more specific/general scenarios. In Secs. 6 & 7, they discuss methods to tune the two parameters and provide experimental evidence of their theoretical results.\n\n#### Strengths & Weaknesses\n\nFirst, the strengths: I found the paper to be well-organized, and mostly well-written. It aims to tackle a pretty fundamental problem, and provides some clear and simple results in relation to a simple algorithm. For the statements I checked, the paper was technically sound.\n\nAs for the weaknesses, I found some of the mathematical exposition to be hard to follow. The proofs and sketches could really benefit from some diagrams and perhaps some simple example scenarios. Additionally, I found myself unsure of the practical gains from their algorithm. They make a single comparison to a linear classifier, and it's almost certain that the comparison would not be as favorable against any method that allows for classification in a non-binary fashion (with some level of confidence, and thus some natural level of abstention).\n\n#### Recommendation\n\nBased on the above, I gave a rating of 7. I did not give a higher score, as I am not sure of the practical relevance of the suggested algorithm. On the other hand, the theoretical results seem solid and are of a pretty fundamental nature. I do provide this score with a grain of salt, as I was not able to check all the theoretical statements, which are the backbone of this paper, in my opinion.\n\nUPDATE: I am downgrading my score to a 6. Based on the opinions of my fellow reviewers, it seems that perhaps the theoretical results are based on scenarios that are too simplistic for the community at hand. Moreover, there are clearly some readability issues, based upon the reactions of the other reviewers.\n\n#### Clarification Questions & Suggestions\n\n1. As suggested, perhaps it would be helpful to discuss or consider existing methods that provide classification with some level of confidence. It seems that these automatically provide some notion of abstention when confidence is not high enough. I found it surprising that none of these were mentioned.\n2. I noticed that the supplementary material contains a few references on examples of the subspace threat model. I feel like a sentence in the main text would be helpful to provide some context for the relevance of this threat model.\n3. In the proof of Thm. 4.1, the existence of a label \\\\(y^*\\\\) with volume fraction less than 0.5 exists by virtue of having at least two labels. Even with an abstention option, existence would hold, I believe.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Nn4VfbeoKPr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 studies the power of abstention in robust classification. A classifier that has the power of abstention can refuse to answer the query because it is unsure of the answer. For robust classification, the abstention power enables the classifier to refuse adversarial queries, if the query is detected as an adversarial example.\n\nThe paper first shows a negative result on the possibility of robust classification. After reading the statement of theorem and the proof multiple times, it is not clear what the theorem is stating. The theorem only says that the adversary can flip the label using arbitrary large perturbations, which seems to be a trivial statement. In the comments bellow I have listed several questions to get a clear understanding of this theorem.\n\nAfter the negative result, the paper studies the effect of abstention by showing a positive result on the 1-nearest neighbor classifier. The idea is simple, whenever the query is far from its nearest neighbor in the training set, the classifier refuses to answer. This clearly provides some lower bound on the robustness as long as the data is well separated. This result cannot be used for actual image datasets that are used in practice because 1NN will definitely not have good accuracy even without abstention. Also, the images are not well-separated at all. However, the authors still run some experiments by considering the adversarial attacks in the feature space (the noise is added in the feature space instead of input space.). They show that using some good feature representation, they can get acceptable robust accuracy using their method. However, it is important to note that this will not have any meaningful effect on the real datasets classification tasks. \n\nAs for evaluation, I find the idea of paper in studying the provable effect of abstention exciting. However, the theorems that are proved lack clarity and significance. I suggest the authors to re-write the theorem in a more understandable way with all parameters clearly explained. From a technical point of view, it seems that the theorems that are proved are not really relevant to adversarial perturbations. The definitions of adversarial perturbations seem arbitrary and not aligned with standard definitions. \n\nComments/Questions to Authors:\n\nTheorem 4.1: \n1- The current statement of theorem is trivial. You don't provide any bound on the size of perturbation which makes the theorem not very useful.\n2-The statement of theorem says a random vector v. What does that mean? Are you considering robustness to random noise or adversarial noise? If so, how is this related to adversarial examples?\n3-In the proof it says R=\\frac{r_\\delta \\sqrt{n_2}}{\\delta} is large enough to provide some property about the balls of size r_\\delta. Doesn't this statement require some distributional assumptions for data distribution?\n4- There are already some negative results about adversarial robustness that the paper could refer to. \n\nTheorem 5.1: \n\n1-The definition of \\Epsilon^x_adv is not clear at all which makes the whole theorem not really understandable.\n2-It sounds to me that the bound on the error could be well beyond 1? If not, you should explain why. what if n3=n2?\n3-  What does this sentence mean? \" The adversary is allowed to corrupt F(x) with arbitrarily large perturbation in a uniform-distributed subspace S of dimension n3\". Again, what do you mean by uniform distributed?\n4-In general, defining adversarial perturbation in a subspace with smaller dimension seems not standard. Did you choose this type of perturbation for a specific reason or just for the sake of proving the theorem?\n5- The proof of this theorem does not sound to be rigorous. Are you assuming that without any perturbation, the 1NN classifier is 100% accurate?", "extra_scores": {}, "extra_text": {}}, {"review_id": "N-zOMKKhmd1", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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: The authors propose a connection between abstention and robustness to adversarial examples. Specifically, the authors contend that without the ability to abstain, any classifier can be fooled by an adversarial perturbation in the feature space. They additionally provide results and experiments concerning the proper selection of a hyperparameter that tunes the abstention.\n\nPros: The authors include many theoretical analyses. A good effort is made to address the problem from several relevant angles. \n\nCons: \n\nThe paper is very difficult to read. \n - The introduction does not provide a clean line of thought motivating the paper. I am not aware that the attack model considered, that of an adversary allowed to make arbitrarily large moves in a subset of feature space, with no constraints on the input space, exists elsewhere in the literature. The work cited (Brown et al. 2018) requires that unrestricted adversarial examples remain unambiguous to human judges.\n\n - The abstract cites results for \"any classifier\" when in fact the result seems to be for a nearest-neighbor style classifier, which is unusual given that the setting is deep networks.\n\n- The variables used throughout are difficult to keep track of.\n\nMajor issues:\n\n- Theorem 4.1: This is obviously not true for all classifiers. The proof is very difficult to follow, and there are no useful details given in Figure 1. The result seems like it may be true by virtue of the fact that KNN with K=1 defines a hyperplane between any two points. Then a randomly chosen vector with probability 1/2 + epsilon inevitably crosses such a hyperplane eventually, but there's no reason to believe such a value in feature space could be reverse engineered or even lies within the range of F.\n\n- The testing in Section 7.1 does not seem to include the use of non-adversarial test samples. In evaluating whether or not a threshold is too strict to be of use, it would be necessary to evaluate on in-domain test samples as well as the training set. These results seem likely to be overfit to the training data. \n\n- The testing setup is unclear. Perhaps there are further details in the referenced papers, but it is not even clear to me how many classes are in the set. Is it only two, given the baseline of a linear classifier?\n\n- The clarity of the paper is severely lacking. It is difficult to follow the contribution of many of the theorems, especially concerning their generality or lack thereof\n\nGiven that I find these issues too concerning to recommend publication, I have not carefully checked all of the proofs.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of abstention in robust classification. A number of issues were identified in the formal framework and the writing was also not up to scratch. The authors should take into regard the very many constructive suggestions made by the reviewers in preparing a revision.
Decision: Reject