Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness
Authors: Ambar Pal
Jeremias Sulam
Rene Vidal
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial Robustness
Geometry in Data
Low Dimensional Modeling
TL;DR: Adversarial examples are provably avoidable when data distributions are concentrated

Abstract: The susceptibility of modern machine learning classifiers to adversarial examples has motivated theoretical results suggesting that these might be unavoidable. However, these results can be too general to be applicable to natural data distributions. Indeed, humans are quite robust for tasks involving vision. This apparent conflict motivates a deeper dive into the question: Are adversarial examples truly unavoidable? 
In this work, we theoretically demonstrate that a key property of the data distribution -- concentration on small-volume subsets of the input space -- determines whether a robust classifier exists. We further demonstrate that, for a data distribution concentrated on a union of low-dimensional linear subspaces, utilizing structure in data naturally leads to classifiers that enjoy data-dependent polyhedral robustness guarantees, improving upon methods for provable certification in certain regimes.

Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness
Ambar Pal ambar@jhu. edu
Jeremias Sulam jsulam1 juuu. edu
René Vidal vidalr@upenn edu
Abstract
The susceptibility of modern machine learning classifiers to adversarial examples has motivated theoretical results suggesting that these might be unavoidable. How- ever, these results can be too general to be applicable natural data distributions. Indeed, humans are quite robust for tasks involving vision. This apparent conflict motivates deeper dive into the question: Are adversarial examples truly unavoid- able? In this work, we theoretically demonstrate that key property of the data distribution concentration on small-volume subsets of the input space deter- mines whether a robust classifier exists. We further demonstrate that, for data distribution concentrated on a union of fow-dimensional linear subspaces, utilizing structure in data naturally leads to classifiers that enjoy data-dependent polyhedral robustness guarantees, improving upon methods for provable certification in certain regimes.
Introduction, Motivation and Contributions
Research in adversarial learning has shown that traditional neural network based classification models prone to anomalous behaviour when their inputs are modified by tiny, human-impercepptbble perturbations. Such perturbations, called adversarial examples, lead large degradation in accuracy of classifiers [55]. This behavior is problematic when such classification models are deployed in security sensitive applications. Accordingly, researchers have and continue to come up with defenses against such adversarial attacks for neural networks.
Such defenses [49, 60, 42, 22] modify the training algorithm, alter the network weights, or employ preprocessing to obtain classifiers that have improved empirical performance against adversarially corrupted inputs. However, many of these defenses have been later broken by new adaptive attacks [1, 8J. This motivated recent impossibility results for adversarial defenses, which aim to show that all defenses admit adversarial examples. While initially such results were shown for specially parameter- ized data distributions [18), they were subsequently expanded to cover general data distributions on unit sphere and the unit cube [48], as well as for distributions over more general manifolds [12].
On the other hand, we humans are an example of a classifier capable of very good (albeit imperfect [17]) robust accuracy against bo-bounded attacks for natural image classification. Even more, large body of recent work has constructed certified defenses [11. 63, 10, 29, 19, 54] which obtain non-trivial performance guarantees under adversarially perturbed inputs for common datasets like MNIST, CIFAR-10 10 and ImageNet. This apparent contention between impossibility results and the existence of robust classifiers for natural datasets indicates that the bigger picture more nuanced, and motivates closer look at the impossibility results for adversarial examples.
Our first contribution is to show that these results be cireumvented by data distributions whose mass concentrates on small regions of the input space. This naturally leads to the question of whether such construction necessary for adversarial robustness. We answer this question in the affirmative. formally proving that successful defense exists only when the data distribution concentrates on an
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

exponentially small volume of the input space. At the same time, this suggests that exploiting the inherent structure in the data is critical for obtaining classifiers with broader robustness guarantees.
Surprisingly, almost' all certified defenses do not exploit any structural aspects of the data distribution like concentration low-dimensionality. Motivated by our theoretical findings, study the special case of data distributions concentrated near union of low-dimensional linear subspaces, to create certified defense for perturbations that go beyond traditional l, nnomm bounds. We find that simply exploiting the low-dimensional data structure leads to a natural classification algorithm for which we can derive norm- corm-independent polyhedral certificates. We show that our method can certify accurate predictions under adversarial examples with an lp norm larger than what can be certified by applying existing, off- the-l methods like randomized smoothing [1 I]. Thus, we demonstrate the importance of structure in data for both the theory and practice of certified adversarial robustness.
More precisely, we make the following main contributions in this work:
1. We formalize notion of (e, connenntraiiin of a probability distribution in Section 2, which states that g assigns at least 1 - mass to a subset of the ambient space having volume O (-ne)). We show that (e, 8) cconcentrattion of is necessary condition for the existence of any classifier obtaining at most 8 error over q, under perturbations of size e.
2. We find that (e, concentraaiio is too general to be sufficient condition for the existence of robust classifier, and we follow up with a stronger notion of concentration in Section which is sufficient for the existence of robust classifiers. Following this stronger notion, we construct an example of a grrongly-concentratie distribution, which circumvents existing impossibility results on the existence of robust classifiers.
3. We then consider data distribution q concentrated subspaces in Section 4. We construct classifier for g that is robust to perturbations following threat models more general than bp- Our analysis results in polyhedral certified regions whose faces and extreme rays are described by selected points in the training data.
union of low-dimensional linear
4. We perform empirical evaluations MNIST in Section 5, demonstrating that our certificates are complementary to existing off- the-shelf approaches like Randomized Smoothing (RS), in the sense that both methods have different strengths. In particular, we demonstrate region of adversarial perturbations where our method is certifiably robust, but RS not. We then combine method with RS obtain certificates that enjoy the best of both worlds.
2 Existence of Robust Classifier Implies Concentration
We will consider classification problem over X' x y defined by the data distribution p such that X is bounded and y {1, 2, K). We let qs denote the conditional distribution Px for class k y. We will assume that the data is normalized, i.c.. X BN, (0, 1), and the boundary of the domain is far from the data, i.c., for any x qs, an adversarial perturbation of &g norm at most e does not take x outside the domain X.2
We define the robust risk of a classifier f: X >>> y against an adversary making perturbations whose lg norm is bounded by as?
R(f,) c)
Pr (x:2))>p
A3 Be, (2, such that f(ā) + v).
We can now define a robust classifier in our setting.
Definition 2.1 (Robust Classifier). A classifier g is defined to be (e, 8)-robust the robust risk against perturbations with & norm bounded by is most d, i.e., if Ríg. e) S 6.
The goal of this section is to show that if our data distribution p admits an (c, 8c robbst classifier, then p has be concentrated. Intuitively, this means that p assigns a "large" measure to sets of "small" volume. We define this formally now
See Section 6 for more details.
2 Mooe details in Appendix
Note that for f (x) to be defined, it is implicit that X' in (1).

---

Definition 2.2 (Concentrated Distribution). A probability distribution over a domain X' C R=" said be (C, c. conccentrat if there exists subset S S X such that q(S) 2 but Vol(S) I Cexpí -in ne). Here, Vol denotes the standard Lebesgue measure on RR,, and ((S) denotes the measure of S under 9-
With the above definitions in place, are ready to state our first main result.
Theorem 2.1. If there exists an (r, -oobust classifier I for a data distribution p. then at least one of the class conditionals q1, .2.............................. qK, say 9b. must be (C,e,8)-co co-ccettteete Further, if the classes are balanced, then all the class conditionals are (Cmax: concentrated Here, C== Vol(x; f(x) = k}, and Cmax = maxę Vol(r: f(x) = k} are constants dependent on f.
The proof is natural application of the Brunn-Minkowske theorem from high-dimensional geometry, essentially using the fact that an e-shrinkage of a high-dimensional set has very small volume. We provide a brief sketch here, deferring the full proof to Appendix A.
Sketch. Sketch. Due to the existence of robust classifier f. i.e., R(f.e) S ò, the first observation is that there must be at least one class which is classified with robust accuracy at least 1 - 6. Say this class is k and the set of all points which do not admit an e-adversarial example for class is S. Now, the second step is to show that S has the same measure (under 9b) as the e-shrinkage (in the & norm) of the set of all points classified as class k. Finally, the third step involves using the Brunn-Mar Minkowski theorem, to show that this e-shrinkage has a volume ((exp(-nee), thus completing the argument.
Discussion on Theorem 2.1. We pause here to understand some implications of this result.
Firstly, recall the apparently conflicting conclusions from Section 1 between impossibility results (suggesting that robust classifiers do not exist) and the existence of robust classifiers in practice (such as that of human vision for natural data distributions). Theorem 2.1 shows that whenever a robust classifier exists, the underlying data distribution has to be concentrated. In particular, this suggests that natural distributions corresponding to MNIST, CIFAR and ImageNet might be concentrated. This indicates a resolution to the conflict: concentrated distributions must somehow circumvent existing impossibility results. Indeed, this is precisely what we will show in Section 3.
Secondly, while our results are derived for the &2 norm, it is very hard extend this reasoning to general l, norms. In other words, whenever a classifier robust to f--norm perturbations exists, the underlying data distribution must be concentrated.
Thirdly, Theorem 2.1 has direct implication towards classifier design. Since now know that natural image distributions are concentrated, one should design classifiers that are tuned for small-volume regions in the input space. This might be the deeper principle behind the recent success [66] of robust classifiers adapted to f,.-ball like regions in the input space.
Finally, the extent of concentration implied by Theorem 2.1 depends on the classifier f. via the parameters e, 5 and C. On one hand, we get high concentration when is large, ö is small, and C is small. On the other hand, if the distribution admits an (e, -robust classifier such that C is large (e.g., a constant classifier), then we get low concentration via Theorem 2.1. This is not limitation of our proof technique, but a consequence of the fact that some simple data distributions might be very lowly concentrated, but still admit very robust classifiers, e.g., for a distribution having 95% dogs and 5% cats, the constant classifier which always predicts "dog" is quite robust.
We have thus seen that data concentration is a necessary condition for the existence of robust classifier. A natural question is whether it is also sufficient. We address this question now
3 Strong Concentration Implies Existence of Robust Classifier
Say our distribution is such that all the class conditionals 91, 92. 9k are (C, 8) conneentta.te Is this sufficient for the existence of a robust classifier? The answer is negative, as we have not precluded the case where all of the l are concentrated over the same subset S of the ambient space. In other words, it might be possible that there exists a small-volume set S C X such that qu (S) is high for all k. This means that whenever data point lies in S, it would be hard to distinguish
3

---

which class it came from. In this case, even an accurate classifier might not exist, let alone a robust classifier'. To get around such issues, we define stronger notion of concentration, as follows.
Definition 3.1 (Strongly Concentrated Distributions), A distribution p is said to be (e,5, -strrongyy- concentrated if each class conditional distribution qu concentrated over the set Sk C X such that (Sk) 2 1 1 8, and qk (Ux* $ S % where St denotes the e-expansion of the set S in the lg norm, i.e., S = =xx: E E S such that | x - c}.
In essence, Definition 3.1 states that each of the class conditionals are concentrated on subsets of the ambient space, which do not intersect too much with one another Hence, it is natural expect that we would be able to construct a robust classifier by exploiting these subsets. Building upon this idea, we are able to show Theorem 3.1:
Theorem 3.1. If the data distribution p is (, -isstrongyy-comccentttteddd then there exists an (e, 5 + -robustt classifter for p.
The basic observation behind this result is that if the conditional distributions qu had disjoint supports which were well-separated from each other, then one could obtain a robust classifier by predicting the class & on the entire e-expansion of the set S₁ where the conditional q: concentrates, for all k. To go beyond this idealized case, we can exploit the strong concentration condition to carefully remove the intersections at the cost of at most 7 robust accuracy. We make these arguments more precise in the full proof, deferred to Appendix B, and we pause here to note some implications for existing results.
Implications for Existing Impossibility Results. To understand how Theorem 3.1 circumvents the previous impossibility results, consider the setting from [48] where the data domain is the sphere g--1 far E R" ||>|||2 = 1). and have binary classification setting with class conditionals 9 and 92. The adversary is allowed to make bounded perturbations w.r.t. the geodesic distance. In this setting, can be shown (see [48, Theorem 1]) that any classifier admits e-adversarial examples for the minority class (say class 1), with probability at least
(- 71 -
1 - Olgz 8 exp
(2)
2
where 0igy = - q (x) depends on the conditional distribution Qı, and 33 is a normalizing constant that depends on the dimension n. Note that this result assumes little about the conditional g1- Now, by constructing a crongly-coocentratee data distribution over the domain, we will show that the lower bound in (2) becomes vacuous.
Example 3.1. The data domain is the unit sphere S equipped with the geodesic distance d. The label domain is {1,2}. P is an arbitrary, but fixed, point lying on Sn-1, The conditional density of class 1, i.e. 9ı is now defined as
P
Fd otherwise
(1(x)
C sin" Pd( 0,
where C' 0.1 a normalizing constant. The conditional density of class 2 is defined be uniform over the complement of the support of qı, i.e. 92 = Unif([ E g--1; d(x, P) > 0.1)). Finally, the classes are balanced, i.e., (1) (2)=
Figure 1: A plot of qı. Redder colors denote a larger density, and the gray plane denotes the robust classifier.
The data distribution constructed in Example 3.1 makes Eq. (2) vacu- ous, as the supremum over the density @i is unbounded. Additionally, the linear classifier defined by the half-space {x: (z, P) S cos(). is robust (Appendix C provides a derivation of the robust risk, and further comments on generalizing this example). Example 3.1 is plotted for 3 dimensions in Fig.
'Recall that classifier not accurate at a point (z, y). i.e., (x) A y. is by definition not robust at x. as a perturbation is already sufficient to ensure f(r + v) # y- MMore detailed discussion in Appendix G.

---

Compatibility of Theorem 3.1 with existing Negative Results Thus, we see that strongly con- centrated distributions are able eircumvent existing impossibility results on the existence of robust classifiers. However, this does not invalidate any existing results. Firstly, measure-conee concentrtoocnnttiiooono based results [48, 18, 12] provide non-vacuone guarantees given a sufficiently flat (not concentrated) data distribution, and hence do not contradict our results. Secondly, our results are existential and do not provide, in general, an algorithm to construct a robust classifier given a dtrongly-oncentrre distribution. Hence, we also do not contradict the existing stream of results on the computational hardness of finding robust classifiers [6, 56, 47J. Our positive results are complementary to all such negative results, demonstrating a general class of data distributions where robust classifiers do exist.
For the reminder of this paper, we will look specific member of the above class of strongly concentrated data distributions and show how we can practically construct robust classifiers.
4 Adversarially Robust Classification on Union of Linear Subspaces
The union of subspaces model has been shown to be very useful in classical computer vision for a wide variety of tasks, which include clustering faces under varying illumination, image segmentation, and video segmentation [57]. Its concise mathematical description often enables the construction and theoretical analysis of algorithms that also perform well in practice. In this section, will study robust classification on data distributions concentrated on a union of low-dimensional linear subspaces. This data structure will allow us to obtain a non-trivial, practically relevant case where we can show a provable improvement over existing methods for constructing robust classifiers in certain settings. Before delving further, now provide simple example (which is illustrated in Fig. 2) demonstrating how distributions concentrated about linear subspaces are concentrated precisely in the sense of Definition 3.1, and therefore allow for the existence of adversarially robust classifiers.
Example 4.1. The data domain is the ball Biz (0, equipped with the fo distance. The label domain is {1,2]. Subspace S₁ is given by S = =xx x² xTer = 03, and S2 is given by S2 = fx: x zeez- = 0}, where e1, 22 are the standard unit vectors. The conditional densities are defined as
f(a) =
91
f(a)
q1 = Unif((x: ||0 < 1, |r e1 S -/2]), and,
90
42 Unif((x: ||=1|00 S 1,
T e2l S e= //2)),
where a >> 0 is a large constant. Finally, the classes are balanced, i... py (1) = py (2) = 1/2. With these parameters, 91, 92 are both (0.5, a/n - 1, conceenntrd over their respective supports. Ad- A robust
2c) strooggy-cooncntraate classifier I can be constructed following the proof of Theorem 3.1, and it obtains robust accuracy R(J,e) S Se=0/2 + 2e. See Ap- pendix D for more details.
ditionally, p is (e, (c,0,e
Figure 2: A plot of qı (or- ange), 92 (violet) and the deci- sion boundaries of f (dashed).
We will now study a specific choice of p that generalizes Example 4.1 and will let move beyond the above simple binary setting. Recall that we have a classification problem specified by a data distribution p over the data domain X' x y (0, 1) x {1. K}. Firstly, the classes are balanced, i.e., PY (k) = 1/K for all k E y. Secondly, the conditional density, i.c., = Px]Y= is concentrated on the set 5 n X, where S& is low-dimensional linear subspace, and the superscript denotes an 7-xxpansion, for a small 7 > O.
For the purpose of building our robust classifier, we will assume access to a training datasct of M clean data points ($1, V1), (52, .2...... (sM. B/M, such that, for all i, the point s; lies exactly on one of the K low-dimensional linear subspaces. We will use the notation S = [$) $2,... S.y] for the training data matrix and y = (V/, U2........................ MMr) for the training labels. We will assume that M is large enough that every x E S₁ can be represented as a linear combination of the columns of S.
Now, the robust classification problem we aim to tackle is to obtain a predictor g: - y' which obtains a low robust risk, with respect to an additive adversary A that we now define. For any data-point x ~ p. A will be constrained to make an additive perturbation w such that diste, (x + v, U,S.) < In other words, the attacked point can have & distance at most from any of the linear
5

---

subspaces Si...., Sk. Note that A is more powerful than an & fy-bounded adversary as the norn of the perturbation ||la|2 might be large, as might be parallel to a subspace.
Under such an adversary A. given a (possibly adversarially perturbed) input x; it makes sense to try to recover the corresponding point s lying the union of subspaces, such that x: + n, such that ||r2]|2 S E. One way to do this is to represent as a linear combination of a small number of columns of S, i.e., x Sc + n. This can be formulated as an optimization problem that minimizes the cardinality of c, given by ||c|lo. subject to an approximation error constraint. Since such problem hard because of the to norm,,, we relax this to the problem
min ||c|] s.t. || - Scil2 S e.
(3)
Under a suitable choice of X, this problem can be equivalently written as
A
min e,e
|c||| + 1 Ilell s.t. x = Sctee
(4)
for which we can obtain the dual problem given by
max(a, d)
2X |d12 s.t. |S S 1.
(5)
Our main observation is to leverage the stability of the of active constraints of this dual obtain robust classifier. One can note that each constraint of Eq. (5) corresponds to one training data point
8; when the 7th constraint is active at optimality, s; is being used to reconstruct z. Intuitively, one should then somehow use the label y/ while predicting the label for x. Indeed, we will show that predicting the majority label among the active y/ leads to robust classifier.
We will firstly obtain a geometric characterization of the problem in Eq. (5) by viewing it as the evaluation of a projection operator onto certain convex set, illustrated in Fig. 3. Observe that for
> O, the objective (5) is strongly concave in d and the problem has a unique solution, denoted by di (z). is not hard show that this solution can be obtained by the projection operator
dx(x)= = arg min |Ar d|la s.L. |SS dllco - 1 Proj (Ax),
(6)
d
where K is the polar of the convex hull of +.S Denoting T = [S. -S,, we can rewrite Problem (6) as di (x) = (arg ming ||A - d/12 sub. to T d 1). We now define the set of active constraints as
Ax(x) {4:
13.
Geometry of the Dual (5). is illustrated in Fig. 3, where $1, 82 are two chosen data-points. The blue shaded poly- tope K At X = X1, the point di lies in the in- terior of K Hence, Ax(x) is empty and supp(c"(x) also empty. As À increases, non-empty support is obtained for the first time at X = 1/Tko (z). For all A2 in the red shaded polyhedron, the projection di (x) = Projg=(A2p)
8% 1r
1o (20)
d iz)
lies on the face F. As À increases further we reach the green polyhedron. Further increases in A do not change the dual solution, which will always remain at the vertex dig (z).
K"
Geometrically, (x) identifies the face of K" which con- tains the projection of Ar, if Ax(x) is non-empty (oth- erwise, Ar lies inside the polyhedron Kº). The sup- port of the primal solution, (x)), is subset of Ax, i.e. supp(c" (x)) S (z). Note that whenever two points, say xr x', both lie in the same shaded polyhedron (red or green), their projections would lie on the same face of K We now show this formally, the main theorem of this section.
K
Figure 3: Geometry of the dual problem
(5). See description on the left.
Theorem 4.1. The of active constraints A defined in (7) is robust, ie.. Ax(x') = Ax(x) for all Xx' E C(x), where C(x) is the polyhedron defined as
C(x)= = F(x)+
(8)

---

with F K being facet of the polyhedron K that projects to, defined as
F(x) F(x)= a t 1, vt Ax(x)
{
dd 1, otherwise
and V being the cone generated by the constraints active at (i.e., normal to) F, defined as
V(x)
Σ
att; a, 20 E Ax(x)
(10)
(EAx(a)
The proof of Theorem 4.1 utilizes the geometry of the problem and properties of the projection operator, and is presented Appendix E. We can now use this result to construct robust classifier: Lemma 4.2. Define the dual classifier
9x(x) = AGGREGATE((y:: t, E Ax(x))),
(11)
where AGGREGATE, is any deterministic mapping from set of labels V, e.g. MAJORITY. Then, for all x' E C(x) as defined in Theorem 4.1, 9x is certified to be robust, iee,, 9x(x') = 9x(x).
Implications. Having obtained certifiably robust classifier g. pause understand some implica- tions of the theory developed so far. We observe that the certified regions in Theorem 4.1 are not spherical, i... the attacker can make additive perturbations having large Eg norm but still be unable to change the label predicted by (see Fig. 4). This is in contrast to the & bounded certified regions that can be obtained by most existing work on certification schemes, and is result of modelling data structure while constructing robust classifiers. Importantly, however, note that we do not assume that the attack is restricted the subspace.
Connections to Classical Results. For c = O, Eq. (3) is known as the primal form of the Basis Pursuit problem, and has been studied under variety of conditions
S in the sparse representation and subspace clustering literature [20, 13, 50, 64, 30, 25]. Given an optimal solution c* c"(x) of this basis pursuit problem, how columns in the support predict the same label, i.e., y/ is identical for all i E supp(c" (x)). Indeed, this ideal case well studied, and is ensured by necessary [25] and sufficient [50, 64, 30] conditions on the geometry of the subspaces SI,..., Sx. Another situation could be that the majority of the columns in the support predict the correct label. In this case, could predict Majorityl (vs : supp(c" (x)))) to ensure accurate prediction. Theorem 4. allows us to obtain robustness guarantees which work for any such aggregation function which can determine single label from the support. Hence, our results can guarantee robust prediction even when classical conditions are not satisfied. Lastly, note that our Theorem 4.1 shows that the entire active set remains unperturbed results in [54], this could be relaxed for specific choices of maps acting on the estimated support.
accurately predict the label y One ideal situation could be that all
light of the recent
5 Experiments
In this section, we will compare our certified defense derived in Section technique called Randomized Smoothing (RS) [11], which can be used to obtain state-of-the-art certified robustness against la perturbations. RS transforms any given classifier f: X + y to certifiably robust classifier gts X' + y by taking majority vote over inputs perturbed by Gaussian noise (0, I²I), i.e.
popular defense
R$ (x) = Smooth, (f) = argmax max ge
Pr (f(x + v) = k)) kEy u0N(0,002))
(12)
Then, at any point RS can be shown to be certifiably robust to l2 perturbations of size at least RS (a) o where p maXkey: Pry=W(0,0=1)((f2 + v) k:) denotes the maximum probability of any class under Gaussian noise.
not immediately obvious how to compare the certificates provided by our method described above and that of RS, since the sets of the space they certify are different. The certified region
'In reality, the choice of the noise distribution is central to determining the type of certificate one can obtain [41, 63]. but Gaussian suffices for purposes here
7

---

Ours
Our + Randomized Smoothing
Randombeed Samolling
True Eg Cérlilicale
Figure 4: Comparing polyhedral and spherical certificates. Details in text.
obtained by RS, CS (x) = { || - E||2 S r(x)). ) is sphere (orange ball in Fig. 4). In contrast, certificate Cx (z) from Theorem 4.1 is a polyhedron (resp., blue trapezoid), which, in general, is neither contained CRS (z), nor a superset C (z). Additionally, our certificate has no standard notion of size, unlike other work elliptical certificates [14), making size comparison non-trivial. To overcome these difficulties, we will evaluate two notions of attack size: in the first, we will compare the &2 norms of successful attacks projected onto our polyhedron, and in the second, we will compare the minimum & norm required for a successful attack. We will then combine our method with RS to get the best of both worlds, i.e., the green shape in Fig. 4. In the following, we present both these evaluations on the MNIST [28] dataset, with each image normalized to unit &g norm.
Comparison along Projection Cxx).. For the first case, investigate the question: Are there perturbations for which our method is certifiably correct, but Randomized Smoothing fails? For an answer this question in the affirmative by obtaining adversarial example
input point z, for g such that I lies inside our certified set CA (I)). Then, this perturbation v x T is certified by our method, but has & norm larger than RS (I) (by definition of the RS certificate).
To obtain such adversarial examples, we first train a standard CNN classifier f for MNIST, and then use RS² to obtain the classifier g.S. Then, for any (zz, y). we perform projected gradient descent to obtain T x" by performing the following steps times, starting with zd + z:
I. x + Projer, (x.c) (x'-1 + V Lossi RS ()))))))))))))))))))))))))))()
x + (r)
(13)
Unlike the standard PGD attack (step I), the additional projection (step II) is not straightforward. and requires us to solve quadratic optimization problem, which can be found in Appendix F. We can now evaluate go on these perturbations to empirically estimate the robust accuracy over Cx. i.e.
ProjsttionRobuustAcccc =
Pr J.SDTPNNIBT
[ E Beg (x, c) n (x()) such that g (x) + v)
The results are plotted in Fig. 5, as the dotted curves. We also plot the certified accuracies? for comparison, as
1.00
Ours Certified
the solid curves. We see that the accuracy certified by RS drops below random chance (0.1) around = 0.06 (solid red curve). Similar to other certified defenses, RS certifies only a subset of the true robust accuracy of a classifier in general. This true robust accuracy curve pointwise upper-bounded by the empirical robust ac- curacy curve corresponding to any attack, obtained via
Projected Robust Accuracy
90.02 Empirical
0.75
90.00
Certified
BS
Empirical
0.50
DS
Certified
0.25
the steps I, II described earlier (dotted red curve). We
then see that even the upper-bound drops below random chance around = 0.4, suggesting that this might be a large enough attack strength that adversary only constrained in le norm is able to fool general classi- fier. However, we are evaluating attacks lying on our certified set and it is still possible to recover the true
0.00
0.00
0.25
0.50
0.75
1.00
Attack Strength
Comparing RS with Our method for adversarial perturbations computed by repeating Steps I, II (13).
Figure 5:
Further details (e.g., smoothing parameters, certified accuracy computation) are provided in Appendix F.

---

class (blue solid curve), albeit by our specialized classifier 9Λ suited to the data structure. Ad- ditionally, this suggests that our certified set contains useful dlass-specffie information this is indeed true, and we present some qualitative examples of images in our certified set in Appendix F. To summarize, we have numerically demonstrated that exploiting data structure classifier design leads to certified regions capturing class-relevant regions beyond e--balls.
Comparison along lg balls. For the second case, we ask the question: Are there perturbations for which RS is cer- rifiably correct, but our method not? When an input
1.00
point r has a large enough RS certificate r (R)(x) 2 fu. some part of the sphere Be, (R. RS (z)) might lie outside
Ours 0c
Certified Accuracy
0.75
Rs
our polyhedral certificate Cx(z) (blue region in Fig. 4),
IBS
In theory, the minimum ro required can be computed via
0.50
an expensive optimization program that we specify in Appendix F. In practice, however, we use a black-box attack [9] to find such perturbations. We provide qualita- tive examples and additional experiments on CIFAR-IO in Appendix F.
0.25
Combining Our Method with RS. We now improve our certified regions using randomized smoothing. For this purpose, we treat our classifier Р사 as the base classifier f in (12), to obtain (gaothh(ga) (abbreviated as Ours" R.). We then plot the l2 certified accuracy" [11, Sec 3.2.2] in
0.000
0.025
0.050
0.075
0.100
Certified Radius
Figure 6: Comparing Certified Accuracy after combining our method with RS.
Fig. 6, where note that, as opposed to Fig. 5, the attacks are not constrained to lie on our certificate anymore.
As final remark, we note that our objective in Fig. 6 was simply to explore RS as method for obtaining an f2 certificate for our method, and we did not tune our method or RS for performance. In particular, believe that wide array of tricks developed in the literature for improving RS performance [41, 45, 63] could be employed to improve the curves in Fig. 6. We now discuss our work in the context of existing literature in adversarial robustness, and sparse representation learning.
6 Discussion and Related Work
Our proof techniques utilize tools from high-dimennsonal probability, and have the same flavor as recent impossibility results for adversarial robustness [12, 48, 47]. Our geometric treatment of the dual optimization problem is similar to the literature on pparse-reprssennatiion [13, 20] and subspace clustering [50, 51, 64, 25), which is concerned with the question of representing a point æ by the linear combination of columns of a dictionary using sparse coefficients c. As mentioned in Section there exist geometric conditions on S such that all such candidate vectors are beobspace-preserviie i.c., for all the indices i in the support of c, it can be guaranteed that s; belongs to the correct subspace. On the other hand, the question of classification of point x in a union of subspaces given by the columns of S, or subspace classification, has also been studied extensively in classical pparse-rpreesnnttiin literature [62, 61, 7, 27, 65, 65, 65, 39, 23, 32). The predominant approach is to solve an & minimization problem to obtain coefficients c so that Sc e, and then predict the subspace that minimizes the representation error. Various global conditions can be imposed on S to guarantee the success of such an approach [62], and its generalizations [15, 16). Our work differs from these approaches in that we aim to obtain conditions on perturbations to x that ensure accurate classification, and as such we base our robust classification decision upon properties of solutions of the dual of the ε problem.
Our results are complementary [44, 5J, who obtain a lower bound on the robust risk R(f, e), in a binary classification setting, in terms of the Wasserstein distance D between the class conditionals qu and qı, i.e., R(f,c) 2 1- D(qu, Q1). Using this result, [44, 5] roughly state that the robust risk increases as the class conditionals get closer, i.e., it becomes more likely to sample ~ qo, x' ~ 91. such that || - x'| S e. In comparison, for two classes, our Theorem 3.1 roughly states that for low robust risk, go and g should be concentrated on small-volume subsets separated from one another. Thus, the message is similar, while our Theorem 3.1 derived in more general multi-class setting. Note that [44, 5] do not explicitly require small-volume subsets, but this is implicit, as D(go. 91)

---

is large due to concentration of measure when go. 91 do not concentrate on very small subsets. We provide an analogue of the empirical results of [44. 5] in Appendix F.6.
Our notion of concentration is also related to concentration of a measure 14, as considered in [35, 36, 70]. which denotes how much the ju-measure of any set blows up after expansion by Under this definition, the uniform measure has a high degree of concentration in high dimensions, and this is called the concentration of measure phenomenon. In contrast, our Definition 2.2 of concentrated data distributions can be seen as a relative notion of concentration with respect to the uniform measure μ. in that we call class conditional q concentrated when it assigns large g-measure to a set of very small volume, (i.e., (SS) is high whereas Ju(S) is very low). In essence, Definition 2.2 defines concentration relative the uniform distribution, whereas [35, 36, 70] define concentration independently. Definition 2.2 is useful in the context of adversarial robustness as it allows us to separate the concentration of data distributions (which is unknown) from the concentration of the uniform measure in high dimensions (for which there is good understanding). This allows us to derive results the realizaleeell setting, where errors are measured against a probabilistic ground truth label Y. which is strictly more general than the realizable setting which requires deterministic ground truth classifier f*, As a result of this realizable setting, the analysis in [21, 35, 36, 70J needs to assume non-empty error region A for the learnt classifier g with respect to f", in order to reason about e-expansions A+c. The results in [35, 36] indicate that the robust risk grows quickly as the volume of A increases. However, humans seem to be case where the natural accuracy is not perfect (e.g., we might be confused between a 6 and poorly written 5 in MNIST), yet we seem to be very robust against small & perturbations. This points slack in the analysis in [35, 36], and our work fills this gap by considering expansions of a different family of sets.
Finally, our work is also related to recent empirical work obtaining robust classifiers by denoising a given input æ of any adversarial corruptions, before passing it to a classifier [46, 38]. However, such approaches lack theoretical guarantees, and might be broken using specialized attacks [40]. Similarly, work on improving the robustness of deep network-based classifiers by adversarial training off the data-manifold can be seen as an empirical generalization of our attack model [24, 37, 69, 33). More generally, it has been studied how adversarial examples relate to the underlying data-manifold [53, 26, 34]. Recent work also studies the robustness of classification using projections onto single low-dimensional linear subspace [3, 2, 43]. The work in [3] studies an the attack model of bounded f2, for attacks, and they provide robustness certificates by obtaining guarantees the distortion of data-point x as it is projected onto a single linear subspace using projection matrix IT. In contrast, our work can be seen as projecting perturbed point onto union of multiple low low-dimensional subspaces. The resultant richer geometry allows us to obtain more general certificates.
7 Conclusion and Future Work
To conclude, we studied conditions under which robust classifier exists for given classification task. We showed that concentration of the data distribution on small subsets of the input space is necessary for any classifier to be robust to small adversarial perturbations, and that stronger notion of concentration is sufficient. We then studied a special concentrated data distribution, that of data distributed near low-dinensional linear subspaces. For this special case of our results, we constructed a provably robust classifier, and then experimentally evaluated its benefits w.r.. known techniques.
For the above special case, we assume access to clean dataset S lying perfectly on the union of low-dimensional linear subspaces, while reality one might only have access to noisy samples. In light of existing results noisy subspace clustering [59], an immediate future direction is to adapt our guarantees to support noise in the training data. Similarly, while the assumption of low- dimensional subspace structure in S enables us to obtain novel unbounded robustness certificates, real world datasets might not satisfy this structure. We hope to mitigate this limitation by extending our formulation to handle data lying general image manifold in the future.
Acknowledgments and Disclosure of Funding
We would like to thank Amitabh Basu for helpful insights into the optimization formulation for the largest lg ball contained in a polyhedron. This work was supported by DARPA grant HR001 TRR001120200 12020010.
10

---

NSF grants 1934979 and 2212457, and the NSF-Simons Research Collaboration on the Mathematical and Scientific Foundations of Deep Learning (NSF grant 203 1985, Simons grant 814201).
References
[1] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learming, pages 274-283, PMLR, 2018.
[2] Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, and Aravindan Vijayaraghavan. Adversarially robust low dimensional representations. In Conference on Learning Theory, pages 237-325.
PMLR, 2021.
[3] Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, and Aravindan Vijayaraghavan. Adversar- ial robustness via robust low rank representations. Advances in Neural Information Processing Systems, 33:1 111111191199911 2020.
[4] Amitabh Basu. Introduction to convexity. Optimization, 52:37, 2019.
[5] Arjun Nitin Bhagoji, Daniel Cullina, and Prateck Mittal. Lower bounds on adversarial robustness from optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
[6] Sébastien Bubeck, Yin Tat Lee, Eric Price, and lya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Leurning, pages 831-840. PMLR, 2019.
[7] Raffaele Cappelli, Dario Maio, and Davide Maltoni. Subspace classification for face recognition. In International Workshop on Biometric Authentication, pages 133- Springer. 2002.
[8] Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras. Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint 190..0:900.00700 2019.
[9] Jianbo Chen, Michael Jordan, and Martin Wainwright. Hopskipjjuppattek: A query-efficient decision-based attack. In 2020 ieee symposium on security and privacy (sp), pages 1277-1294. IEEE, 2020.
[10] Ping-ych Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Gold- stein. Certified defenses for adversarial patches. In 8th International Conference on Learning Representations (ICLR 2020) International Conference on Learning Representations, 2020.
[11] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
[12] Elvis Dohmatob. Generalized no free lunch theorem for adversarial robustness. In International Conference on Machine Learning, pages 1646-1654 PMLR, 2019.
[13] David L Donoho and Michael Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via minimization. Proceedings of the National Academy of Sciences, 100(5):2197- 2202, 2003.
[14] Francisco Eiras, Motasem Alfarra, Philip Torr, M Pawan Kumar, Puneet K Dokania, Bernard Ghanem, and Adel Bibi. Ancer: Anisotropic certification via sample-wise volume maximization. Transactions of Machine Learning Research.
[15] Ehsan Elhamifar and René Vidal. Robust classification using structured sparse representation. In CVPR 20 pages 1873-1879, IEEE, 2011.
[16] Ehsan Elhamifar and René Vidal. Block-sparse recovery via convex optimization. IFEE Transactions Signal Processing, 6008):409444107, 2012.

---

[17] Gamaleldin Elsayed, Shreya Shankar, Brian Cheung, Nicolas Papernot, Alexey Kurakin, Ian Goodfellow, and Jascha Sohl-Dickstein. Adversarial examples that fool both computer vision and time-limited humans. Advances in neural information processing systems, 31, 2018.
[18] Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. Advances in neural information processing systems, 31, 2018.
[19] Marc Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transfor- mations via randomized smoothing. Advances in Neural Information Processing Systems, 33:8404-8417, 2020.
[20] Simon Foucart and Holger Rauhut. An invitation compressive sensing. In A mathematical introduction to compressive sensing, pages 1-39. Springer, 2013.
[21] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, Ian Goodfellow, and G Brain. The relationship between high-dimensional geometry and adversarial examples. arXiv preprint / 2018.
[22] Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. In International Conference on Learning Representations, 2018.
[23] Kang-hua Hui, Chun-li Li, and Lei Zhang. Sparse neighbor representation for classification. Pattern Recognition Letters, 33(5):661-66) 2012.
[24] Charles Jin and Martin Rinard. Manifold regularization for locally stable deep neural networks. arXiv preprint arXiv:2003. 042266, 2020.
[25] Mustafa Kaba, Chong You, Daniel P Robinson, Enrique Mallada, and Rene Vidal. nullspace property for subspace- prrepacc-preservng recovery. In Marina Meila and Tong Zhang, editors, Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5180-5188. PMLR, 18-24 Jul 2021.
[26] Mare Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. arXiv preprint arXiv: 1.Xi:01811.0052. 2018
[27] Jorma Laaksonen et al. Subspace classifiers in recognition of handwritten digits. Helsinki University of Technology, 1997.
[28] Yann LeCun. The mnist database of handwritten digits. http://som..ccu...om/eecddmmiit 1998.
[29] Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. Advances in Neural Information Processing Systems, 33:6465-644 2020.
[30] Chun-Guang Li, Chong You, and René Vidal. On geometric analysis of affine sparse subspace clustering. IEEE Journal of Selected Topics in Signal Processing, 1266):120- 2018.
[31] Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics & Statistics, 4(1):66-70, 2010.
[32] Wei Li, Eric W Tramel, Saurabh Prasad, and James E Fowler. Nearest regularized subspace for hyperspectral classification. IEEE Transactions on Geoscience and Remote Sensing. 52(1):477- 489, 2013.
[33] Wei-An Lin, Chun Pong Lau, Alexander Levine, Rama Chellappa, and Soheil Feizi. Dual manifold adversarial robustness: Defense against lp and non-lp adversarial attacks. Advances in Neural Information Processing Systems, 33:3487-3498, 2020.
[34] 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 Learning Representations, 2018.
12

---

[35] Saeed Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody. The curse of concen- tration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3536-4543 2019.
[36] Saeed Mahloujifar, Xiao Zhang, Mohammad Mahmoody, and David Evans. Empirically measuring concentration: Fundamental limits on intrinsic robustness. Advances in Neural Information Processing Systems, 32, 2019.
[37] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pages 9086, 2019.
[38] Seyed-Mohsen Moosavi-Dezfooli, Ashish Shrivastava, and Oncel Tuzel. Divide, denoise, and defend against adversarial attacks. arXiv preprint arXiv:1802.06886, 2018.
[39] Imran Naseem, Roberto Togneri, and Mohammed Bennamoun. Linear regression for face recognition. IEEE transactions on pattern analysis and machine intelligence, 32(11):2106 2112, 2010.
[40] Zhonghan Niu, Zhaoxi Chen, Linyi Li, Yubin Yang, Bo Li, and Jinfeng Yi. On the limitations of denoising strategies adversarial defenses. arXiv preprint arXiv:2012.09384, 2020.
[41] Ambar Pal and Jeremias Sulam. Understanding auggeete training for randomized smoothing. Transactions on Machine Learning Research, 2023.
[42] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense to adversarial perturbations against deep neural networks. In 2016 IEEE symposium on security and privacy (SP), pages 582-597, IEEE, 2016.
[43] Samuel Pfrommer, Brendon G Anderson, and Somaych Sojoudi. Projected randomized smooth- ing for certified adversarial robustness. 2022.
[44] Muni Sreenivas Pydi and Varun Jog. Adversarial risk via optimal transport and optimal couplings.
In International Conference on Machine Learning, pages 7814-7823. PMLR, 2020.
[45] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
[46] Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adversarial attacks using generative models. In International Conference on Learning Representations, 2018
[47] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018
[48] Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adver- sarial examples inevitable? arXiv preprint 1rXiv:/809.022 0000000000004..0.. 2018.
[49] Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Advances in Neural Information Processing Systems, 32, 2019.
[50] Mahdi Soltanolkotabi and Emmanuel J Candes. A geometric analysis of subspace clustering with outliers. The Annals of Statistics, 40(4):2195-2238 2012.
[51] Mahdi Soltanolkotabi, Ehsan Elhamifar, and Emmanuel Candes. Robust subspace clustering. The annals of Statistics, 02(2):669-699 2014.
[52] Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385-633 2004.
13

---

[53] David Stutz, Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6976-6987, 2019.
[54] Jeremias Sulam, Ramchandran Muthukumar, and Raman Arora. Adversarial robustness of supervised sparse coding. Advances in neural information processing systems, 33:21 10-2111,, 2020.
[55] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312,699, 2013.
[56] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry, Robustness may be at odds with accuracy. arXiv preprint arXiv:/805.12/15 2018.
[57] René Vidal, Yi Ma, S Shankar Sastry, René Vidal, Yi Ma, and S Shankar Sastry. Generalized Principal Component Analysis. Springer, 2016.
[58] Václav Vorácek and Matthias Hein. Provably adversarially robust nearest prototype classifiers. In International Conference on Machine Learning, pages 22361-22382 PMLR, 2022.
[59] Yu- Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. In International Conference on Machine Learning, pages 89-97. PMLR, 2013.
[60] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2019.
[61] John Wright, Yi Ma, Julien Mairal, Guillermo Sapiro, Thomas S Huang, and Shuicheng Yan. Sparse representation for computer vision and pattern recognition. Proceedings of the IEEE, 9866):1031-1044, 2010.
[62] John Wright, Allen Y Yang, Arvind Ganesh, Shankar Sastry, and Yi Ma. Robust face recognition via sparse representation. IEEE transactions on pattern analysis and machine intelligence, (1())220-- 2000.
[63] Greg Yang. Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference Machine Learning, pages 10693-10705. PMLR, 2020.
[64] Chong You and René Vidal. Geometric conditions for subspace- sparse recovery. In International Conference on Machine Learning, pages
PMLR, 2015.
[65] Guoxian Yu, Guoji Zhang, Zili Zhang, Zhiwen Yu, and Lin Deng. Semi-supervised classification based on subspace sparse representation. Knowledge and Information Systems, -301), 2015.
[66] Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Rethinking lipschitz neural networks for certified l-infinity robustness. arXiv preprint arXiv:2210.01787, 2022.
[67] Richard Zhang, Phillip Isola, Alexei Efros, Eli Shechtman, and Oliver Wang. The unrea- sonable effectiveness of deep features as perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 586-595, 2018
[68] Shangzhi Zhang, Chong You, René Vidal, and Chun-Guang Li. Learning a self-expressive network for subspace clustering. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 12393-12403, 2021.
[69] Shufei Zhang, Kaizhu Huang, Jianke Zhu, and Yang Liu. Manifold adversarial training for supervised and semi-supervised learning. Neural Networks, 140:282-29 209-2, 2021.
[70] Xiao Zhang and David Evans. Understanding intrinsic robustness using label uncertainty. arXiv preprint arXiv: 100.020000 2021.
14

---

A Proof of Theorem 2.1
We will make the technical assumption in Section precise. Recall that all quantities are normalized so that X' is an l2 ball of radius 1, i.e., X Br (0, 1). Recall that que X' R2o denotes the conditional distribution for class E 3/, having support Qu. We will assume that there a sufficient gap between the supports and the boundary of the domain, i.e., Qx S Big (0, c), and that the fg-adversarial attack has strength S c, for some constant e, say c= 0.1.
Theorem 2.1. If there exists an (e, (e,ouurobuss classifier I for a duta distribution p. then at least one of the class conditionals qı, .2......... ,, say Uk must be (yconceecceeeeelleeeeed Further, if the classes are bulanced, then all the class conditionals are (Cmax: &, - -o0cceenntttted Here, C' Vol(x: f(x) = k}, and Cmax maxx Vollx: f(z) k} are constants dependent on f.
Proof. Note that the definition (1) of (e, 80obuussss may be rewritten
R(f,e)
Σ Px P (Xadmits an e-adversarial example|Y k))py
= E (1(x E x: B E B2x, c) such that f(ø) * kt)pyy (y k))
(14)
where ((S) denotes the q-measure of the set S. We given f such that R(S,e) S 6, and want to find a set S C X' over which p concentrates.
R(f,e) 5
Σ q (((xx: As e ((x, n such that f(Ø) # k))ppr S
(15)
Since Σn Py = k) = 1, the LHS in (15) is a convex combination, and we have
3K (1( E x: E B(x, E) n X such that f(x) + k3) S 6,
(16)
q: (U) S 8, where
U -=
(a X:: 3a E B(r, e) n XX such that f(t) + kj.
We will express qg. (U) in terms of the classification regions of
Let A C X denote the region where the classifier predicts k. i.e. A (x E:: f(x) = =k). Define
A to be the set of all points in A at &a distance atleast from the boundary, i.e. A = (x
A: B(x, c) S A). Now consider any point x E X. We have the following mutually exclusive, and exhaustive cases:
1. x lies outside A, i.e., x & A. In this case, a E U trivially as f(xx) o k.
2. x E A, and the entire e-ball around x lies inside A, i.e. B(x, e) S A. In this case, every point in the e-ball around x is classified into class k and has no eaavversarial example for class k. Note that the set of all these points is A by definition.
3. x A. and some portion of the e-ball around lies outside A, i... B(I,e) & A. and, there is point ā E B(x, <) n X such that f(ī) * k. In this case, F is an adversarial example for x, and & E U.
4. x A, and some portion of the e-ball around lies outside A, i.e. B(x,e) Z A, but there is no point T E B(x, t) O such that f()) * k. This can happen only when for all T E B(x,e) <) \ A we have 7. & X. In other words, any perturbation that takes outside A, also takes it outside the domain X. This implies that B(r, e) g X', which in turn means that the distance of from the boundary of X is atmost
We see that U comprises of the points covered in cases (1) and (3). Recall that we assumed that any point having distance less than 0.1 to the boundary of does not lie in the support of qg. But all points covered in case (4) lie less than e-close to the boundary, and S 0.1. This implies that qu
15

---

assigns 0 measure to the points covered in case (4). Together, cases (1), (3) and (4) comprise the set (X (A A ) Thus, we have shown
q (U) = q: (X' \ A (A
5.
(17)
Next, we will show that the set A is exponentially small, by appealing to the Crunn-Minkowske inequality, which states that for compact sets E, F R",
Vol(F + F) 2 Vol(
Vol(F)
where Vol is the n-dimensional volume in R" and E F denotes the minkowski sum of the sets E and F. Applying the inequality with = A and F Bz, (0, c). we have
Vol(A- + Be, (0, c)) 2 Vol(A + Vol Vol(Ba, (0, Vol(A) 2 Vol(A + eVol (0, 1))
Vol(A)* 2 Vol(A +Vol(A)
VoI(A-))
Vol(A) (1
Vol(A-9) < Vol(A)( - c)" < exp(-e)
Vol(AT9) S Ō Cexp(-nc).
(18)
where C = Vol(A). From (17) and (18), we see that qu is (C, e, conccenntrr Additionally. use the fact that every term of (15) be atmost K6, and apply
the classes balanced, the above reasoning for each class to conclude that each qk is (Cmax: e, -ooocconcettratedd for some suitable choice of Cmax, e.g., Cinxx max; Volf2 X: (x) = k).
B Proof of Theorem 3.1
Theorem 3.1. If the data distribution p is (c,ō, 5, ( -inssrorngyycconneenttteddddd then there exists an (c, 5 + ro-buuttt classifier for p.
Proof. For each & E {1, 2..,. K}. let Sy be the support of the conditional density Qu- Recall that S+rr is defined be the e-expansion of the set S. Define C& to be the e-expanded version of the concentrated region S₁ but removing the e-expanded version of all other regions Sp., as
C₁ (S \ UK' nxX
We will use these regions to define our classifier f: X - 2 K} as
1, if E C₁
2,
if E C2
f(x)=
:
K,
if E CR
1,
otherwise
We will show that R(S,e) < 4.4 which can be recalled to be
R(f,c)= Σ (fx E X: 3 B(r,c) such that f()) + k))py (v = =b).
In the above expression, the yu mass is over the of all points X that admit e-adversarial example for the class k. as
U+ (r E X: Er B(x, c) X' such that f()) + k).
(19)
Define C e to the set of points in Cs at distance atleast from the boundary of Cs as C {o Cs: B(x,e) e) C Cz). For any point e Uk. can find z B(z, e) from (19) such that
16

---

I ÿ Ck, showing that & Ck- Thus, Up is a subset of the complement of C i... Up S X' C , and we have
R(S,) Σ (u:(U))r -
k).
Now we will need to show few properties of the e-contraction. Firstly, for set M = N NNO, we have M - - 5 which can be seen as
M (x: x M, (xx,
{a: e N, O, B(z
Secondly, for set M No, where denotes complement, we have M (N+o), This can be seen as
M u = (x: a M( C ( N, ((z,
= =xx: x & N, Va' E B(x,e) N
(r: Yo' B(x, c) [
= 9M = (x: 3r's B(x,e) EN
= N+
Thirdly, for set = O. we have M =N N- (09)~+bg by the first property, and then N =00)===0==00----) N n (O+e)e by the second property. This implies
(N 1 - 10+-
Fourthly, for set M = U,O, we have M = N n first and second properties, we get M N+ + Applying the above properties to C we have
Taking e-contractions, and applying the
C = (Stt) \ UK " 788=
= (Sa \ (URSeN St te) nx
2 (Sk U nx
Recall that g (x- q(2) = 1 by the support assumption. Hence, we have
au (Sx) db (UN 2 (1- - (C( 2 Ub (Sx \ UW
- 1- (C= S t Finally, Σx (y k) 1, we have R(f,c) + by convexity.
C Proofs for Example 3.1
Let 0o S x/2. We will show that the following classifier f is robust in the setting of Example 3.1:
11, if 0g
f(x) 22 otherwise
Let C1 = fo E Sn-1: x } be the set of points classified into class by f. Similarly, let C2 1 C1 be the set of points classified into class 2. The robust risk of f (measured w.r.t. perturbations the geodesic distance d) can be expanded as
Ba(f.c) c) 0.5g (d+ (C2)) 0.5gg(d+
(20)
where d+*(S) denotes the e-expansion the set S under the distance d. Let S 0o (otherwise, the first term is 1/2). Recall that the class conditional is defined
(((( Pj
if ddx, S 0o otherwise
21 (x)
sin
0,
17

---

where is a normalizing constant which ensures that @1 integrates to 1, i.e., co fg.. 91 Then, 92 was defined to be uniform over the complement of the support of qı i.. = Unif({ e g--1: d(x, 0o
We can expand the first term of Eq. (20) as
2i (dt+ (C2)) = qn (1(dtt (C2) \ C2) + (1(2
(fz: 0 < d(z, C2) S { +0.
Now for any x & C2. we have d(x, C2) = 0n 1 (x, P). Hence, {r: 0 d(x, C2) < {) fx: 0.1 I d(x, P) 0g). Let ((x)) denote the angle that makes with P. Then, the geodesic distance is d(r P) (()) The earlier set is the same as the set of all points satisfying 0g - e S ((x) < 1. This
nothing but the e-base of the hyper-spherical cap having angle 0g.
We continue,
q1(12: 0o - < d(x, P) 00) qı ((x: 8o -Es 0o))
With a change of variables, the above can be evaluated as
(d(x, PI)
(1(10- S ((x) < ooo) =
Cp 60 (0-r(0(a)<0 sin(d P))n-22t dr
(0)
Co 80 (sin 00000m22/ppp |nn 2 2( E s--1: ((x) = 0))
where 2 is the -2-2222- 2-dimensional volume (n 1-dimensional surface area). Now, 2 gm-1; ((x) - 0}) nothing but the volume an slice of the hypersphere gn-1 This slice is in itself hypersphere in R==1, having radius sin 0. Thus, its volume is the same the volume of the ga-2, scaled by (sin 0) We continue.
80 J
(0)
80
(0)
o (sin (sin Un 2n 2(x E ((x) -0)
(sin (sin0)~~2dh 2)n
(sin 1)
2
8
no
(0))d
10
For illustration, we can take (0) 1, giving (Ct) e/C from the above integral, with Cy = 1 (0)d0 to fo-
We can now follow the same process as above, and expand the Eq. (20) as
q2(dt* = (n-1((x: 0g S ((x) S 0o + E), where 1 again the n 1-dimensional volume. We use the following formula [31] for the surface area of a hyperspherical cap (valid when S </)):
Mn- ((x: 0 < 0(x) S aa) = m(a) def 0.5 (S" (S"
1
n1 n 1111
where I(,,)) ) is the incomplete regularized beta function. Letting da. = m(T/2) mm(m////2 12) m(0)). we continue,
+ (m( m())))
if + 00 S 4/2
dop
Co (e(tt((C)))
+ m - mm(0p + - 7/2)),
if if < t 0o S
=
dop
else
dog
The risk from class 1 dominates till reaches around n/2, then the risk from class 2 shoots up. We plot the resultant risk in Fig. (left).
Having presented the basic construction, we now comment on how Example 3.1 can be generalized. Firstly, we can vary the support of Qı, to have it cover a different fraction the sphere. For instance, we can set 0g = π. 2 to get modified as
if d(r P) m/2 otherwise
(x)
C sin d(z.P)
0,
18

---

R4f44
0.6
R.(9.4)
0.6
R2(9.4)
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.1
</4
6/2
0x/4
0.1
3/4
4/2
3x/4
6/4
x/2
3e/4
Figure 7: Robust risk for classifiers for concentrated distributions on the sphere Sn-1, for dimension n 100. (Left): plot of Ra(f. <) w.I. p1. As c grows from to 0.1, class is the major contributor the risk. At 0.1, all points in class admit adversarial perturbation, taking them class 2. As grows further, the risk for class grows slowly, till reaches close to x x/2, after which it blows up abruptly due the high-dimensional fact that most of the mass of the uniform distribution lies near the equator of the sphere. (Middle): plot of Rg(g, <) w.r.t P2- As we make the support of the concentrated class larger, the distribution admits a classifier g with slightly improved robustness for smaller values (S. 0.1). (Right): A plot of Ra(g,e E) w.r.t. P3: Finally, as both class conditionals are made concentrated, the classifier g becomes quite robust.
and let d/ be uniform over the complement of the support of d1 Along with balanced classes (i.e., P(Y=1) 1) P(Y 2) = 1/2), this gives the data distribution p2. The robust classifier would now be given by the half-space {æ: d(x, P) < π 2/. The risk over can be computed as earlier, and is plotted Fig. 7 (middle).
We can take this example further, and make both i and d2 concentrated. This can be done, for instance, by setting ol q1, and setting &² as follows:
if ifd 7/2
(x)
C sin
de.
otherwise
where P the antipodal point of P. both class conditionals are now concentrated, the halfspace separating their supports becomes quite robust, This can be seen in the Fig. 7 (right).
Lastly, vi be taken to be rapidly decaying function for even greater concentration and lesser robust risk, e.g., (0)) exp(-0)
D Proofs for Example 4.1
Example 4.1. The data domain is the ball Bi (0, 1) equipped with the E distance. The label domain (1,2). Subspace S₁ is given by S1 = {z: x T e1 = 0}, and S2 is given by S₂ {x: TTey e2 0}. where E1, e2 are the standard unit vectors. The conditional densities are defined as
eil s - and. = Unif({#: ||]| S 1, 1, T
22 Unif({2: |00| S 11, T e2l S -a-aaaa00 -a/))))
where a > is a large constant. Finally, the classes are balanced, i.e., = 1/2. With these parameters, q1, 92 both (0.5, a/n 1, concenttate over their respective supports. robust classifier can be constructed
Additionally, p is (e, 0, e, + 2e) 3->-stronngy-comcettaaeet following the proof of Theorem 3.1, and it obtains robust accuracy R(f,e) I e --//2 /2 + 2e. See Appendix for more details.
It would be helpful to have Fig. 8 in mind for what follows.
19

---

(()
ST Ste-0/2
f(0)= =2
S2 12--0112
6
a
Figure 8: A plot of ạ (orange), d2 (violet) and the decision boundaries of f (dashed).
We will demonstrate that the classifier / illustrated in Fig. 8 has low robust risk. We define f' for any Boc (0, 1), follows (let 7 9)):
if 2 2/2 t ral 2 7/2+ if |2 S 5/2 + c, mi 2 7/22+2 +c.
f(x) =
2,
1,
otherwise
The reason for splitting the cases for predicting 1 into two subcases, is that we will only need to analyse the first subcase and the second will not contribute to the robust risk.
Defining U, to be the set all points æ which admit an adversarial example for the class 1, i.e. U1 {x: 3ø such that || x112 f(x) 2}. It is clear that
U1 C {x: |xa| 2 7/2 or |a2| < 5/2 + 26}.
U2 is defined analogously, and
U2 S {z: |22| 2 7/2 or |2 S 3/2 2c}.
Now, R(f,e) = 0.5g. (U1) + 0.5g2 (U2). We look the first term, and simplify an upper bound:
an (U1) < ((x: |z|| 7/2 or |22 S 1/2 2e)
$ ((x: |21| 2 7/2)) (qx (x2 S 7/2 2c)
- 10+1((1:: |x2| </2 2.)).
(21)
Now, recall that @1 = Unif((x: |aa| $ 7/2)), hence the expression in (21) evaluates to
a (fx: |22|| 5 Vol((x: r: |z1| < <//2})
Vol(fz: [aa </2 2c, |21| S 7/2})
2n 2n-2 (7 + 4c)
0.57 2e
The situation for is symmetric, and hence U2 (U2) = 0.5(7 + 4e). Adding them together, we see that the robust risk upper bounded by
R(f.) S 0.5(e-* + 4c)
20

---

For the concentration parameters, note that the support of i.e. 51 [z: |1 < 2/ =]}
has volume 72" 2nm1 exp(-a) 0.5 2" exp((n(a/n))) - 0.5exp(-n(a/n 1)). Hence, is (0.5, a/n 1,0) concentrated over Sy. Similarly, 22 is (0.5, 1,00::/mm100)cccccmemee concentrtte over S2 = (r: |2z S 7/2, | S 1). Finally.
(1 (1(11/210 1, | 7/2, ||22| +/2+ =2n 227 122
-0.5% + 2c
E Proof of Theorem 4.1
Theorem 4.1. The of active constraints A defined in (7) is robust, ie., Ax(x) Ax(x) for all Ax' E C()), where C(x) is the polyhedron defined as
C(x) F(x:) + (z)).
(8)
with F C K being a facet of the polyhedron K that projects to, defined as
{
d d 1, Ax(x)
F(x) - d 1, otherwise
(9)
and V being the cone generated by the constraints active at (i.e., normal to) F, defined as
V(x)
Σ (EA)(*)
ad:: os 2, E Ax(x)
(10)
Proof. Let Ar' E C(x) defined in (8). There exist I E F(x), V(x) such that Ar' We will show that the projection of Ax' onto F is given by f. Recall that
Ax(x) (1:: (1i,d)(1')) 1}, where (x') Proj (ro)
(22)
Choose any 2 E k Recall that Proj xc (Ax') = min || Xx 1|2. Consider the objective,
|| - Xx 1|3 = [| - r12 = || f13 + ||=112 2(= - f)
(23)
We will show that (a f, v) is negative. Consider any t, E Ax(), and observe that (2, S. 1, as E K However, from the definition of F(x) recall that (f, 1. This implies that f,) 0. Using the fact that v E (zz,, we expand the inner product as
(2 f,2) = Σ
ariz - f.t) < 0.
(24)
(EAx(x)
Using (24) in (23) to obtain
|| - Xx 112 || 2
f112 11 0.
(25)
The minimizer above is obtained Projg (Az') = f. Finally, d (2') = Proj (Ax') = f F(x). The theorem statement then follows from the definition of F(x).
f C(x), and hence we have shown that for all Ax' C(z).
F Further Experimental Details and Qualitative Examples
F1
Comparison along Projection on C)
In this section, we will provide more details on attacking classifier with perturbations that lie on our certified set Cx.
21

---

Details of the Projection Step II in (13) Recall from Theorem 4.1 that Cx(x) is defined as the Minkowski sum of the face (x) (9) and the cone (z) (10). Given an iterate x², we can compute its projection onto Cx(x²) ) by solving the following optimization problem
(n0) arg min || x||2 s.t. Cx(x")
Now every Cx can be written as d where d E F(x"), V(x"). d is such that t'd = 1 for all t2 Ax(x",, and t d otherwise. Then, is such that Ei,EAx ast, for some 0; 2 0. Recall that T [t1, 12,,t.,,,2.. denotes the matrix containing the training data-points as well as their negations. Let the matrix A E [dx]AA(=*) contain all the columns of T in Ax (x=" and let A₂ E (2xxx) contain all the remaining columns. Then the objective of the optimization problem above can be written
min ||= Aia d12 s.t. A 1. 0
1,
(26)
(26) a linearly constrained quadratic program, and can be solved by standard optimization tools. In particular, we use the qp solver from the python cvxopt library.
Visualization of the Certified Set In Fig. 9, we visualize the set Ax ie., the set of active constraints at the optimal solution of the dual problem, for several in the MNIST test set. It can be seen that (x) contains images of the same digit as x in most cases. This is expected, as taking the majority label among (x) gives an accuracy of around 97% (solid blue curve in Fig. 5). Note that all these images E (x(x) are also contained in the certified set, Cx(x), which can be seen as t + O, with F (z), and 0 E (x)..
Ax (x)
Ax
0
0
1
/
/
/
/
2
2
2
2
2
2
/
/
1
/
/
/
6
6
6
6
6
6
2
2
2
2
2
3
3
5
3
4
4
4
4
7
7
7
7
7
7
6
6
6
6
6
6
8
5
8
3
8
3
8
8
8
8
8
8
7
7
7
7
7
7
6
6
6
6
6
4
4
4
4
4
4
8
8
8
8
8
8
Figure 9: A visualization of the set of active constraints Ax (z:) for several æ. Atmost members of
Ax (x) are shown for every
22

---

Visualization of Attacks restricted to the Certified Set In Fig. 10, we visualize the attacks restricted to our certified set C₃ computed by (13) for the classifier 90.02- We observe that we can identify the correct digit from most of the attacked images, but the randomized smoothing classifier is incorrect at higher 6. A small number of these attacked images are close to the actual class decision boundary, and the class is ambigous. This is expected, both due to the inherent class ambiguity present in some MNIST images, as well as the large we are attacking with. For all these images, the prediction of our classifier 9A is certified to be accurate. For comparison, the RS certificate is unable to certify anything beyond 6 2 0.06.
I.
2
3
7
7
8
9
0
/
2
3
7
8
9
0.09
0.2
7
2
3
C
7
8
9
2
2
3
8
8
0.4
2
2
0.6
Figure 10: A visualization of attacks on the RS classifier 90.02 restricted to our certified set Cx obtained by (13). Different rows plot different attack strengths e. Whenever an image is misclassified, the red annotation on the top left shows the class predicted by RS
F.2 Comparison along & balls
Exact Certification for 9> In this section, we first state and prove Theorem 4.1 that allows us to exactly compute the Eg certified radius for our classifier gA at any point x.
Lemma F.1. For all x' E C(x) as defined in Theorem 4.1, we have gx(x') 9x(x). Additionally, for all ||l||| S (x(x) we have ga (x + v) = 9x(x), where
ro(x)= min - (z. u)
(27)
sub. to
||u||= 1,
(u.4) S AAA E Ax(x), (u, & 1 Vo Vo ex)(F(x)))
where ex)(F(z)) is the set of extreme points of the polyhedron F(x).
Discussion Before presenting the proof, let us ponder over the result. We see that (27) involves solving an optimization problem having as many constraints as the number of extreme points of the polyhedron F(x). In general, this can be very large in high dimensions, and hence computationally inefficient to compute. As a result, while Lemma F. provides an exact certificate in theory, it is hard to use in practice without further approximations.
Proof. Recall that given set Ax(x), the polyhedron C(x) is defined in (8) as
C(x) F(x) V(z).
(28)
where P(x) is a polyhedron, and V(x) is cone given as the conic hull of Ax i.e, V(x)
cone(A, (A)e(A)))) )z)). We want to find the size r(z) of the largest f, ball centered at x, i.e., B(x, r(x)). that
can be inscribed within C(x). From convex geometry [4], we know that any polyhedron can be described as an intersection over halfspaces obtained from its polar, C as
C(x) (u) (u,
(29)
23

---

where H (u. {x: (u.z) & 0}. The distance of x from the boundary of (a)) is the same as the smallest distance of from any halispace (29). However, this distance is simply
dist(æ; H (u, 0)) =
(30)
In other words, we can expressing C(x) as the intersection over halfspaces whose normals lie in C (x)).e.. r(x) min - (z, u), sub. to ||u||2 u (²()))
(31)
All that left is to obtain a description (x)). This can be done by first expressing C(x) in standard form, as
C(z) = conn(xxx(((())) + (xx)))
(32)
where ext( F(x:) denotes the extreme points of the polyhedron F(x), conv(.) denotes the convex hull and cone(-) denotes the conic hull. Now we can apply a theorem in convex geometry obtain the polar ([4, Th. 2.79]) as
(4,4) S S0W, Ax(x) iu 0) S Va ext(F(x))
(²(x)= (²())= u:
(33)
Combining (31) and (33), we obtain the lemma statement. Finally, we note that as Theorem 4.1 shows that Ax Ax (z) for all Ax' E C(x), and the classifier gx(2) purely a function of Ax(x), we have that 9x (a') 92 (x) for all Ax E C(z).
Black Box A Attacks on 9X Since our classifier J사 is not explicitly differentiable with respect to its input, we use the HopSkip/ump [9] black-box attack to obtain adversarial perturbations that cause misclassification. The obtained attacked images, and the pertubation magnitude are shown in Fig. 11.
P
0.74
1.0
0.6
0.22
0.48
0.47
0.99
0.75
0.17
0.75
Figure 11: A visualization of attacks on our classifier obtained by the HopSkipJump black box attack [9]. The label predicted by gx shown red annotation the top left. The la perturbation magnitude is shown at the bottom. Note that the values are not nice fractions because they are set by the HopSkipJump attack using binary search find the minimum attack strength that causes misclassification.
F.3 Details of Randomized Smoothing Certificates
For obtaining the certified accuracy curves using Randomized Smoothing [11] (solid lines in Figs. and 6), we follow the certification and prediction algorithms for RS in [11, Sec 3.2.2]: given a base classifier f and a test image z, we use no 100 samples from an isotropic gaussian distribution \/ a) to prediction the majority class g RR((()) (z). We then use n 100 samples to estimate the prediction probability PA under N (0, or) with confidence atleast 0.999. If P.a is at least 0.5, we report the certified radius σ (px). Otherwise, if PA < 0.5, we abstain and return certified radius of O.
Evaluating the Dual Classifier 9x We normalize each image in the MNIST dataset have unit l norm, and resize to 32 x 32, We pick 10000 images at random from the training set to obtain our data matrix S I 1024x 10000. We now pick test point æ, and then solve the dual problem (5) with À = 2, to obtain the dual solution d (x). This allows us to then obtain the set of active constraints A (x) in (7). Then, we use the majority rule as the aggregate function (1 to obtain the classfication output from the dual classifier (x(x). We sample 100 and 500 images uniformly random from the MNIST test set for generating the curves Figs. 5 and 6, respectively. All experiments are performed NVIDIA GeForce RTX 2080 Ti GPU with 12 GB memory.
24

---

E4 Discussion of Computational Cost
The computational complexity of obtaining the certificate C(x) in Theorem 4.1 is dominated by solving the linear optimization problem (6) to obtain the set Ax. which has n + M variables. It is known that practice, the cost of solving LPs is much lower than the worst case [52], and it takes us 11.7 seconds on average on single CPU for each image without parallel processing.
For comparison to other certified defenses (like Randomized Smoothing), perform T = 20 steps of (13), and each Step II of (13) requires solving a quadratic optimization program, given in (26). This is linearly constrained quadratic program. practice takes us 18.1 seconds on average on single CPU for each I without parallel processing.
F55 Experiments on CIFAR-10
We provide experiments for our method applied to CIFAR-1O. To do this, we first embed each CIFAR-10 image into a feature space, designed such that Ey-bounded perturbations in the feature space, i.e. +(x++)), ||e||2 I c, correspond to semantic perturbations in the input space, e.g., distorting the image. Such feature space is obtained following recent popular work in learning perceptual metrics in vision [67]. where the task precisely to learn a feature representation where Eg distances align with human perception. We now use our subspace model on di (X), and perform exactly the experiments in Section 5, and make similar observations: we obtain reasonable robust accuracy using our method (Fig. 12 blue lines), and this accuracy is maintained within our certified polyhedra at high e, where existing defenses are not robust.
Though such experiments showing feature space certificates have appeared in the literature [58], the question of whether the perceptual representation itself susceptible to small adversarial perturbations still remains for future exploration.
CIFAR- 10 (LPIPS Features)
CIFAR- -0 (SENet Features)
Projected Robust Accuracy
0.50
Ours Certified
Projected Robust Accuracy
0.75
Ours Certified
nS
Empirical
BS Empirical
90,32
as
Certified
A Certified
96.34
Empirical
0.50
A AL Empirical
0.25
90.31
Certified
A, fL. Certified
0.25
0.00
0.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Attack Strength
Attack Strength
Figure 12: Comparing Randomized Smoothing (RS) with Our Method from Section 4, for adversarial perturbations computed by repeating Steps I, II from Eq. (13). This figure is the counterpart of Fig. 5, where the MNIST dataset has been changed to (CIFAR-10). and the transformation & is given by (left) 384-dimensional slice of LPIPS [67] features (i.e., output of the third Conv2D layer) and (right) 128-dimensional input features used by SENet [68]. Observation I: Our method retains robustness even when the dashed empirical upper bound for robust accuracy for the RS classifier drops to random chance. Observation 2: Our robust accuracy (solid blue line) gets higher from left to right, the feature space of SENet is closer to a union of subspaces than LPIPS. On the other hand, the left feature space aligns better with human perception than the right feature space.
F.6 Evaluating Theorem 3.1 on Empirical Distributions
The empirical results in [44, 5] create an empirical distribution á by selecting two classes from CIFAR-10. 10, which simply places probability mass 1/N on each of the N samples in the dataset. [44, 5] evaluate their lower bounds on P. and not on the actual real world distribution p. which might be arbitrarily complex. Hence, it is unclear whether the trends observed hold for p. Nevertheless, the
25

---

same experiment can be translated to our setting for any real world dataset, our Theorem 3. would then show the existence of robust classifier for P. We would need to solve discrete optimization problem for finding the concentrated sets in Theorem 3.1. Even though valid only for p, this analysis interesting, and is reported in Fig. 13.
Theorem 3.1 on CIFAR-10
0.75
0.50
0.25
0.00
0.10
0.15
0.20
0.25
Figure 13: Instantiating Theorem 3.1 for the CIFAR-10 empirical distribution. We construct the empirical distribution á which assigns equal probability to each (z, y) pair in the CIFAR-10 test set. This leads to empirical class conditionals .1..... 91o. corresponding to the 10 classes. We set 7 = 0 in Theorem 3.1, and greedily construct the sets S ... S1o: sort all images in decreasing order of their distance to their nearest neighbor in the test set, pick the first m images, and then compute the concentration parameters (minimum separation em and mass o. 1- min; (S.)). We then plot (em, 5m) for several choices of m. Applying Theorem 3.1, each (em, 5m) guarantees the existence of (em: -m.-ro classifier for p.
G Discussion on Strong Concentration
Are Natural Image Distributions Strongly Concentrated? Consider the task of classifying im- ages of dogs cats. Any small &2 perturbation (say of size 0.1) to image of dog is not likely to change it to an image of a cat - the true label (or a human decision) does not change with small perturbations. Let Seat be the set of images that are cats with a high confidence. and similarly for Sdog. What we just said was that any image in the e-expansion of Seat is not likely to be dog, and vice versa. This is precisely the condition of separation in the definition of strong concentration: Idog (Stai) S y, and leat (5tog) dog) I y, for a small
Now, despite the above, the task of practically classifying an image into a dog or a cat is not trivial at all, as the sets Sang and Seat might be very complex. and hence it might be computationally hard to find a predictor (neural network, or any other classifier) for distinguishing Saog and Scat. Using modern deep learning, one is able to learn an approximation to these sets that leads to small standard error, but this approximation is still bad enough that the learned predictor is very susceptible to adversarial examples. This is to say that task of robustly classifying an image into dog or cat is even harder.
Tightness of Strong Concentration In Definition 3.1, we are trying to obtain a sufficient condition for the existence of a robust classifier. There are two parts to Definition 1: the concentration, and the separation conditions. The first is essential, Theorem 2.1 asserts that whenever robust classifier exists for a data distribution, the class conditionals are concentrated (i.c., it is necessary).
As we argued above, the separation condition is not very strong, and should be satisfied by image distributions like MNIST, CIFAR-10 and ImageNet. Let us walk through this condition to see it can be further relaxed. As we note at the start of Section 3, if all the class conditionals were to be concentrated on subsets S₁ that have high intersection among each other, then even benign classification would be hard (i.e., benign risk will be high), let alone robust classification. So, even for the existence of a good benign classifier, is essential for S₁ O Sk. to be close to empty, for all k * K'.
26

---

Now, even if Sy n Spr were almost empty, for a robust classifier, we care about the e-expansions of these sets not intersect. In other words, we do want an e-perturbed cat look like dog. Hence, for the existence of good robust classifier, Ss O S should be close to empty, for all k o k.. This can be generalized in measure terms, require qu (S S for small Upto this, all these conditions are essential for obtaining robust classifier.
Now, note that in Definition 3.1, the expansion is taken for 2c, instead of c. This is where our proof technique for Theorem 3.1 incurs slack of and we believe different approach for constructing the robust classifier might be able to reduce the expansion requirement to e. This could be an interesting future avenue for relaxing Definition 3.1 and thereby strengthening Theorem 3.1.
27


Reviews:
[{"review_id": "x1b2wQENbR", "reviewer": "Reviewer_8n5k", "summary": "This paper first studies the existence problem of a robust classifier from a data concentration perspective. In particular, they prove that the (strong) concentration property of class-conditional data distributions characterizes a sufficient and necessary condition for determining whether a robust classifier exists. This seemingly contradicting result complements existing works on impossibility results of adversarially robust classification [17, 43, 11]. Built upon the assumption that the underlying distribution is concentrated on a union of low-dimensional linear subspaces, the paper proposes a new way to derive robustness certificates by leveraging techniques from sparse representation and subspace clustering. Experiments on MINST are provided as empirical evidence supporting the effectiveness of the proposed certification method.", "questions": "1. Could you provide a detailed discussion with related works [1-4] and explain why data concentration implies different conclusions about the possibility/impossibility of adversarially robust classification?\n\n2. If we assume a human classifier is adversarially robust to image classification tasks, does Theorem 2.1 implies how concentrated the input distribution is? If so, what are the important factors affecting the degree of concentration?\n\n3. Do the constants $c_1$ and $c_2$ in Definition 2.2 depend on the underlying density $q$ and $\\delta$? If so, could you specify their dependencies?\n\n4. Could you clarify the generalizability of the proposed certified defense in Section 4 if the underlying data distribution deviates from the imposed assumption regarding linear subspaces?\n", "limitations": "The paper discusses the limitations and implications of their results well in Section 6.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical results are mostly well-written, and their implications are discussed in detail. I did not check the proof, but I think the results are technically correct. In addition, I very much like how this paper structures its theoretical results: a main theorem followed by a proof sketch and a detailed discussion of its implication.\n\nThe first part of this paper shows a somewhat surprising result compared with existing works deriving impossibility results of robust classification [17, 43, 11]. Assuming a robust classifier exists (i.e., a human classifier), the paper shows that the data distribution has to be concentrated in a small-volume subset in the input space. A robust classifier is guaranteed to exist if the class conditionals are both concentrated and well-separated. Given that human is robust to small, adversarial perturbations exists, these results suggest natural data distributions are likely to be concentrated, and existing impossibility results may be due to unrealistic distributional assumptions.\n\nThe second part of this paper aims to study how to leverage the underlying data structure (i.e., the fact/assumption that data are concentrated on a union of low-dimensional subspaces) for adversarially robust classification. The presented method uses the classical literature of sparse representation, which seems novel to the field of robustness certification. Overall, the paper did a good job of discussing their theoretical results and explaining their broader implications.\n\n", "weaknesses": "Regarding the first part of the paper, I think the presented theoretical possibility results are correct, which complements existing works [17, 43, 11]. However, I want to point out several missing references [1-4]. These works studied the concentration of measure phenomenon and its connection to robust classification/learning. There are some differences, but I believe those existing works are very relevant, thus, should be cited and discussed properly. In particular, your definition of (strongly) concentrated distribution and the notion of concentration of measure introduced in [2] seems different. Also, a key assumption imposed in them [1-4] is that there exists a ground-truth classifier (i.e., a human classifier) and a machine learning classifier is imperfect (see the definition of intrinsic robustness introduced in [3]). In other words, they assume a constant (say 1%) clean error of any machine learning classifier always exists. However, this assumption seems not to be considered in this work. Could you discuss those differences with comparisons to your work?\n\n[1] The Relationship Between High-Dimensional Geometry and Adversarial Examples. Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, Ian Goodfellow. ArXiv: 1801.02774.\n\n[2] The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure. Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad Mahmoody. AAAI 2019\n\n[3] Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness. Saeed Mahloujifar, Xiao Zhang, Mohammad Mahmoody, David Evans. NeurIPS 2019\n\n[4] Understanding Intrinsic Robustness Using Label Uncertainty. Xiao Zhang, David Evans. ICLR 2022\n\nIn addition, I am a little confused about the degree of concentration implied by Theorem 2.1. Theorem 2.1 says that if an $(\\epsilon, \\delta)$-robust classifier exists, all the class conditionals are $(\\epsilon, K\\delta)$-concentrated if they are balanced. This result seems interesting, but from my perspective, a discussion of whether this result holds for most data distributions or only applies to certain distributions is missing. Simply judging from Definition 2.1, there is little clue on what data distribution is concentrated and, more importantly, their degree of concentration. The constants $c_1$ and $c_2$ are vaguely described, so could you explain their dependence on other parameters such as the density function q and $\\delta$? If the data distribution lies on a low-dimensional manifold, does it always imply the underlying distribution is concentrated?  I recommend the authors provide examples of concentrated distributions with a characterization of their degree of concentration. \n\nThe result of Theorem 3.1 is not very surprising. The assumption that the underlying class conditional distribution is strongly concentrated seems strong. To be honest, I am not convinced that this assumption will hold for natural image distributions. Otherwise, image classification would be rather a simple task. Therefore, it would be important for the authors to clarify this in the response. \n\nRegarding the second part, I have to say I am not familiar with the literature on sparse representation. I can understand the motivation and main message of leveraging the underlying data structure, which is interesting. Still, I am concerned about the assumption that data distributions are concentrated on a union of low-dimensional linear subspaces to be too strong to hold in practice. The applicability of your method seems to be heavily dependent on whether the distribution satisfies the imposed subspace assumption. MNIST may be more aligned with such an assumption, but Gaussian-like data distributions such as CIFAR-10 and ImageNet may not be. Therefore, I am not confident that the proposed method will work for other image benchmarks like CIFAR-10.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our paper well written and the results novel and interesting. Here are our responses to your comments:\n\n> Q1. Detailed comparison to [1-4].\n\nThe results in these works support our claims. We detail several aspects below:\n\n---\n\n**Comparison of notions of concentration** \n*Concentration* of a measure $\\mu$ as considered in [2-4] denotes how much the $\\mu$-measure of any set *blows up* after expansion by $\\epsilon$ (i.e., over all sets $A$, with $\\mu(A) \\geq 0.5$ say)  what is the minimum $\\mu(A^{+\\epsilon})$). Under this definition, the uniform measure (in other words *volume*) has a high degree of concentration in high dimensions, and this is called the concentration of measure.\n\nIn contrast, our Defn. 2.2 of concentrated data distributions can be seen as a *relative* notion of concentration with respect to the uniform measure $\\mu$, in that we call a class distribution $q$ concentrated when it assigns a large $q$-measure to a set of very small volume, (i.e., $q(S)$ is high whereas $\\mu(S)$ is very low).\n\nIn short, we define concentration relative to the uniform distribution, whereas [2-4] define concentration independently. Our definition is useful in the context of adversarial robustness as it allows us to separate the concentration of data distributions (which is unknown) from the concentration of the uniform measure in high dimensions (for which there is a good understanding).\n\n**No need for a ground truth classifier**\nGreat point! There exist two settings for robustness in the literature - the realizable setting: measuring errors against a *deterministic* ground truth classifier $f^*$, and the non-realizable setting: measuring errors against a *probabilistic* ground truth label $Y$. In the realizable setting, the best (Bayes) classifier can have a non-zero risk, and thus is strictly more general than the realizable setting. Our analysis directly handles the non-realizable setting, and thus does not require us to assume any perfect ground truth classifier. \n\n**No need for an imperfect classifier**\nAs the analysis of [1-4] is conducted in the realizable setting, they need to assume a non-empty error region (say $1\\%$ as the reviewer mentions) for the learnt classifier $g$ with respect to $f^*$, in order to reason about epsilon-expansions of this region. The results in [2,3] indicate that the robust risk grows fast with the volume of these error regions. However, humans seem to be a case where the natural accuracy is not perfect (e.g., we might be confused between a $6$ and a poorly written $5$ in MNIST), yet we seem to be very robust against $\\ell_p$ perturbations. This points to a slack in the analysis in [2,3], and our work fills this gap by considering epsilon expansions of a different family of sets.\n\nThanks for these useful references, we will discuss them in the paper.\n\n--- \n\n> Q3. What do the constants depend on?\n\n**Constants $c_1, c_2$, and the degree of concentration**\nThe definition of concentration becomes stronger as $c_1$ becomes smaller, and as $c_2$ becomes larger. The constants are determined by the dimension of the input space $n$, and do not depend on any other variable, e.g., $q, \\delta, \\epsilon$. For a general distribution, we cannot say much more about the relationship between $q, \\delta, \\epsilon$. \n\nFor Theorem 3.1, $c_1 = Vol (B_2(0, 1))$, and $c_2 = n$ (Appendix Eq.18). Here, $B_2(0,1)$ is the unit $\\ell_2$ ball in $n$ dimensions, whose volume decays rapidly with $n$ as $n^{-(n + 1)/2}(2 \\pi e)^{n/2}$. We will highlight the above in the paper.\n\n> Q2. Assuming robust human, what does Theorem 2.1 imply?\n\nAssume that a human classifier is adversarially robust for MNIST with robust accuracy $95\\%$ at an attack strength of $0.1$ in $\\ell_2$ norm. We have $\\delta = 0.05$ and $\\epsilon = 0.1$ for Theorem 2.1. The classes are balanced in MNIST, so that all classes are $(0.1, 0.5)$-concentrated. In words, this means that for all classes, there is a subset of the space which contains at least *half* of the class but has volume at most $c_1 \\exp(-0.1 c_2)$, where the constants from the previous paragraph can be used. The factors affecting the degree of concentration are the input dimension $n$, human's robust accuracy, and the attack strength tolerated -- for each factor, higher implies stronger concentration.\n\n---\n> Q4: How well does the method in Sec 4. generalize beyond the subspace case?\n\nOur classifier in Sec 4 can in principle be applied unchanged to any data, albeit the performance is better when the data lies near low dimensional subspaces. We provide empirical evidence for CIFAR-10 for the same in the [global response][1].\n\n--- \n**Other Concerns**\n\n> The assumption that the underlying class conditional distribution is strongly concentrated ... will [not] hold for natural image distributions, otherwise, image classification would be rather a simple task.\n\nWe respectfully disagree, and argue in the [global response][1] that natural image distributions should be strongly concentrated, yet this does not make the natural image classification task trivial.\n\n> Low-dimensional support implies concentration?\n\nYes, a manifold having dimension lower than the ambient dimension $n$ has $0$ volume, and the distribution has measure $1$ on this set, so the distribution is $(\\infty, 0)$-concentrated, which is the \"highest\" concentration possible. This should be seen as an extreme case, our Defn 2.2 considers the natural generalization of this extreme case.\n\n> Provide examples of concentrated distributions.\n\nWe have provided a few examples of concentrated distributions in Examples 3.1, 4.1 in the paper. Ex. 4.1 shows a $(\\alpha, 0)$-concentrated distribution supported near a low-dimensional manifold. Ex 3.1 constructs a concentrated distribution on the unit sphere, and Appendix C (L659+) generalizes Ex 3.1. Thank you for this suggestion, we will make these examples more prominent in the text.\n\n[1]: https://openreview.net/forum?id=JDoA6admhv&noteId=hpTXK3MMPW"}, {"review_id": "sG4XymQKZK", "reviewer": "Reviewer_eEv4", "summary": "The paper shows that adversarial examples can be avoided allowing for robust classification as long as the data distribution obeys certain properties. In particular, they show that the the input data distribution needs to be \"well-concentrated\" and not overlap too much in order to guarantee the existence of a robust classifier with provable certificates. They support their theoretical guarantees with experimental results on MNIST.", "questions": "1. In line 229, do you mean strongly concave? Unless you transform the problem to a minimization problem.\n2. The assumption that adversarial perturbations do not take $x$ outside the domain $\\mathcal{X}$ seems somewhat unreasonable. Is this really necessary? I agree that this is needed for $f(\\bar{x})$ to be well defined, but isn't it even easier to guarantee robustness if it is not defined?\n3. The notion of requiring the data distribution to concentrate on an exponentially small volume of the input space looks closely related to the hardness results from Wang et al. \"Attack of the Tails: Yes, You Really Can Backdoor Federated Learning\". Their results show that adversariabl robustness in FL is provably hard which is the opposite of this work. However, I feel they are somewhat related. Can you comment?\n4. In (1), can the definition be changed to $f(\\bar{x}) \\neq f(x)$? This way robustness and accuracy can be disentangled. It seems somewhat unintuitive that an inaccurate classifier cannot be robust. I would expect that the $0$ classifier is the most robust.\n5. I have perhaps missed this, but I couldn't find any discussion of the computational cost of certifying robustness using this approach. I would like to see the dependence on $d$.\n6. In Figure 5, the \"Ours Certified\" line is 1.0 for all $\\epsilon \\in [0, 1]$. However, the certified region should not be symmetric around $x$, so this doesn't make sense to me.", "limitations": "The authors discuss some of the limitations of their work in Section 6. But I would like them to consider some of my questions above and include those as well if they are relevant.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem of adversarial robustness is extremely important and impactful. Further, in the face of hardness results and well known existence of adversarial examples, this is a difficult problem to tackle\n2. The authors formalize the notion of \"well-concentrated\" distributions very well. I think the idea of distribution-specific robustness is well motivated and the right way to approach this problem.\n3. I think the paper is well written and the mathematical arguments look non-trivial and sound.", "weaknesses": "1. Since this work is primarily a theoretical contribution, I consider this a minor point - I would like to see experimental results done on a few settings larger than MNIST. (say Cifar-10, TinyImagenet)\n2. My main concern with the paper is that Definition 3.1 is possibly too strong. It almost seems like the definition is equivalent to creating a robust classifier since it ensures that the different classes are well separated and well concentrated. Is there some way to interpolate between Definition 2.2 and 3.1 which is the minimum assumptions required to guarantee the existence of a robust classifier?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our paper well written, and our theory interesting. We address your comments below:\n\n> My main concern is that Def 3.1 is possibly too strong. Is there some way to [relax it]?\n\nGreat question. In the [global response][9], we explain why Def 3.1 is not strong, is satisfied by real world distributions, and is $\\epsilon$-close to the minimum set of conditions needed. We will add this discussion to the paper.\n\n> Empirical Results on CIFAR-10?\n\nPlease see the [global response][9] for empirical results on CIFAR-10.\n\n---\n\n> Q4: Can Eq. (1) be changed to $f(\\bar x) \\neq f(x)$? \n\nThe short answer is no, the definition should not be changed. Let us expand further:\n\nLet us call the alternative definition $f(\\bar x) \\neq f(x)$ to be *consistency* of a classifier to avoid confusion. We think (1) is more useful than consistency in the context of our work.\n\n- In the first part of this work, we produced necessary and sufficient conditions for robustness. These considerations largely lose their utility under the consistency definition. For instance, \"if a consistent classifier exists for a distribution p\", then we can say nothing about p, because the $0$ classifier is always consistent everywhere, as the reviewer mentioned. Similarly, sufficiency is also not interesting (\"for any p there always exists a consistent classifier\"). The utility of studying such conditions arises from the interplay of consistency and accuracy.\n\n- (1) also nicely generalizes the notion of standard risk from classical learning theory, which can be seen by setting $\\epsilon = 0$, to recover the definition of standard risk. This is not the case with consistency.\n\n- The above problems arise because $f$ can be a useless classifier, like the $0$ classifier, and be perfectly consistent. To avoid this case, one might wonder whether changing (1) to $f(\\bar x) \\neq f^*(x)$ makes sense, for some ground truth $f^*$. While better than consistency, we still advocate for (1), as going this route requires one to assume a perfect ground truth $f^*$, which we do not need in our theorems.\n\nIn short, (1) combines consistency and accuracy, and is the appropriate object of study in our context.\n\n> Q6: In Figure 5, the blue line is 1.0 for all ε, but the certified region is not symmetric around $x$ - this doesn't make sense.\n\nYes, our certified region $C_\\lambda(x)$ is not symmetric around $x$, as you note correctly. Hence, it requires some care to compare our certificates to others existing in the literature (which are symmetric, in particular Randomized Smoothing RS). We mention these difficulties in the Experiments section around Fig 4, and outline two ways to produce a comparison, the first of which is that we compute adversarial examples for prior work which are constrained to lie on our certified set $C_\\lambda(x)$, via Eq. (13). This gives us a way to empirically estimate the ProjectionRobustAccuracy, which is defined as the robust accuracy of any classifier when adversarial examples are projected onto our certificate set $C_\\lambda(x)$. This is plotted in Fig 5. The \"Ours Certified\" line is 1.0 for all $\\epsilon$ by construction, as the adversarial examples are constrained to lie on $C_\\lambda(x)$, where our classifier is provably certified. \n\nTo be fair to existing certified defenses, we also produce another comparison without this additional projection step, in Fig. 6 - even though our method is not tailored for symmetric certificates, we perform at par with RS. The above is a very condensed description of the experiments, and the reviewer can find more details in the text.\n\n> Q5: Discussion of computational cost.\n\nThe computational complexity of obtaining the certificate $C(x)$ (Thm. 4.1) is dominated by solving the linear optimization problem (6) to obtain the set $A_\\lambda$. We have $n + M$ variables in this linear program, leading to a time complexity of $\\tilde{O}((n+M)^{2.38})$ [A]. It is known that the cost of solving LPs is much lower in practice [B], and it takes us $11.7$ seconds on average a single CPU for each $x$ without parallel processing. \n\nFor comparison to other certified defenses (like Randomized Smoothing), we perform $T=20$ steps of Eq. (13), and each step II requires solving a quadratic optimization program, given in App. F Eq (26). This is a linearly constrained quadratic program. In practice it takes us $18.1$ seconds on average on a single CPU for each $x$ without parallel processing.\n\nThanks for bringing this up, we will add the above to Appendix F.\n\n> Q1: Typo in L229.\n\nIndeed, we mean strongly concave. Thanks for catching that.\n\n> Q2: Adversarial perturbations do not take $x$ outside domain - is this necessary? \n\nThis is a minor assumption: for instance, a small $\\ell_2$ perturbation to an image of a dog cannot take it outside the domain of natural images, i.e., it will still remain a natural image. To remove this assumption, we could have required all of our classifiers to first project the input onto the domain. We found that this step introduces a lot of unnecessary clutter in the theorems, and found it cleaner to present the results with this minor assumption. \n\n> Q3: Comparison to Wang et. al. [1]\n\nIn the setting of federated learning, [1] studies the task of \"backdoor detection\" -- find whether an \"adversary provided network\" $g$ differs from a \"benign network\" $f$ in a small, unknown set of training inputs $S$ called the backdoor. They show that detection is computationally hard in general (Prop. 1), and can also be hard given access only to a first order gradient oracle, even when $f, g$ are simple linear classifiers (Prop. 2). This work is not quite related to ours, except for the fact that they use a exponentially small volume set in the construction for Prop 2.\n\n[A]: Brand, A Deterministic Linear Program Solver in Current Matrix Multiplication Time, SODA 2020\n[B]: Spielman and Teng, Smoothed Analysis of Algorithms\n\n[9]: https://openreview.net/forum?id=JDoA6admhv&noteId=hpTXK3MMPW"}, {"review_id": "xHgqqnePp1", "reviewer": "Reviewer_kZpV", "summary": "This paper gives a theoretical insight into the existence of robust classifiers for avoiding adversarial examples, which may be a potential direction for bridging the gap between human perception and machine intelligence. Specifically, this paper reveals the sufficiency and necessity of data concentration for robust classification. The authors conclude that concentration on small-volume subsets of the input space is the key to avoiding adversarial examples for machine learning. In two experiments, the proposed theoretical results are shown to be effective in improving projected robust accuracy and certified accuracy.", "questions": "Please refer to weaknesses.", "limitations": "Limitations are well-discussed. No potential negative societal impact is found.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The research problem is quite interesting, and is significant for the development of machine robustness and safety.\n- This paper is well-organized. The analyses are rigorous and solid.", "weaknesses": "- The main theoretical results are based on $\\ell_2$-normed adversarial training, whether the conclusions are still applicable on $\\ell_\\inf$ norm is unknown.\n\n- The empirical results are insufficient. The experiments are only conducted on every small dataset, whether the theoretical conclusion still holds on larger natural datasets is unknown. \n\n- the conclusion related to subspace training is similar to some existing adversarial training methods, such as [1], [2], which shows that adversarial training on subspace can help alleviate overfitting and improve generalization performance. Is there any difference between these works?  \n[1] Li et al., Subspace adversarial training, CVPR 2022.  \n[2] Li et al., On the adversarial robustness of subspace learning, TIP 2020.\n\n- Another question is that whether the subspace preserve training could be applied to transferred adversarial attacks. Could you make several discussions to justify this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our paper well organized and our theory solid. We address your questions below:\n\n> The empirical results are insufficient. The experiments are only conducted on a small dataset, whether the theoretical conclusion still holds on larger natural datasets is unknown.\n\n**CIFAR-10 Experiments**\n\nWe conducted additional experiments on CIFAR-10 (albeit with some important modifications mentioned below), and obtain similar conclusions as in the paper. The figures for these new results can be found in the PDF attached with the [global response][9]. Details:\n\n- Firstly, we note that our theoretical conclusions (Thm 2.1, 3.1) hold for general data distributions. In the paper, we instantiated our results and provided experiments for distributions supported near a union of low dimensional linear subspaces. \n\n- For our experiments on CIFAR-10, we first embed each CIFAR-10 image $x$ into a feature space $\\phi(x)$, designed such that $\\ell_2$-bounded perturbations in the feature space, i.e., $\\phi(x) + v$, $||v||_2 \\leq \\epsilon$, correspond to *semantic* perturbations in the input space, e.g. distorting the image. Such a feature space $\\phi$ is obtained following recent popular work in learning perceptual metrics in vision [A], where the task is precisely to learn a feature representation where $\\ell_2$ distances align with human perception. Once everything is projected to this feature space, we can utilize our subspace model, and perform exactly the experiments in Sec 5. This style of experiments showing certified robustness after projection to a feature space has appeared in prior literature [B], however the question of whether the perceptual representation $\\phi$ is itself susceptible to small adversarial perturbations remains, and should be a study of future work.\n\n- We find that the results are similar to those observed in the paper: we are able to obtain a non-trivial robust accuracy using our method, and this accuracy is maintained at high epsilons within our certified polyhedra.\n\n> The main theoretical results are based on $\\ell_2$-normed adversarial training, whether the conclusions are still applicable on $\\ell_\\infty$ norm is unknown.\n\n---\n\n**Extensions to $ \\ell_\\infty $**\nExtensions of our methods to $\\ell_\\infty$ perturbations is very much possible, and is a subject of ongoing work. We comment with respect to each of our results, in increasing order of difficulty of extending to $\\ell_\\infty$: \n\n- For the sufficient condition in Sec 3 (Theorem 3.1), our proof technique is in fact quite general, and extends directly to other $\\ell_p$ distances, including $\\ell_\\infty$. \n\n- For the necessary condition in Sec 2 (Theorem 2.1), the general style of the argument mentioned in the proof sketch (L91) still works, the main technical challenge is to show that the $\\epsilon$-shrinkage under the $\\ell_\\infty$ distance has a small volume. We can no longer utilize Brunn-Minkowski, and have to resort to more sophisticated tools from high dimensional geometry. \n\n- For our algorithmic contribution in Sec 4, we studied Problem (3), with a constraint on the $\\ell_2$ norm of the residual $x - Sc$. This constraint would be replaced with the $\\ell_\\infty$ norm. Now the analysis after equation (4) would look quite different with this change, and the associated certificates are also likely to change. \n\n---\n\n**Other Questions**\n> Comparison to [1] Li et al., Subspace adversarial training, CVPR 2022. and [2] Li et al., On the adversarial robustness of subspace learning, TIP 2020.\n\nWe believe [1, 2] are only tangentially related to our work, as we detail below:\n[1] deals with training in a low dimensional subspace of the *weight space* whereas our Sec 4. considers a low dimensional subspace assumption in the *input space*. Further, our certificates are derived against a general $\\ell_2$-bounded adversary, who is *not* restricted to a subspace. \n[2] studies the problem of making Frobenius-Norm-bounded perturbations to a data matrix $X$ to obtain $X'$ such that the distance between the subspaces learnt using PCA, i.e. $\\theta({\\rm PCA}(X), {\\rm PCA}(X'))$ is maximized, for some notion of distance $\\theta$. This is a regression problem, whereas our paper studies a classification problem, with very different attack models. \n\n> Another question is that whether the subspace [preserving] training could be applied to transferred adversarial attacks. Could you make several discussions to justify this?\n\nWe are unsure whether we understand the question. Could the reviewer please clarify what they mean by subspace adversarial training (presumably [1]) \"applied to transferred adversarial attacks\"?\n\n\n[A]: Zhang et. al., The Unreasonable Effectiveness of Deep Features as a Perceptual Metric, CVPR 2018\n\n[B]: Voracek et. al., Provably Adversarially Robust Nearest Prototype Classifiers, ICML 2022\n\n[9]: https://openreview.net/attachment?id=hpTXK3MMPW&name=pdf"}, {"review_id": "ekhdVQjuxe", "reviewer": "Reviewer_Ui3o", "summary": "The paper studies the problem of adversarial robustness in multi-class classification. The authors show that a necessary condition for the existence of an adversarially robust classifier is the condition that at least one of the class conditional ditributions is \"concentrated\" in the sense that most of the probability mass is concentrated on a set of very small volume. The condition of concentration however is not sufficient for the existence of a robust classifier, because one also needs the class conditional ditributions to be well-separated. \n\nThe authors then study adversarial robustness for the special case of data distributions lying on a low-dimensional linear subspace. For this case, they show that robustness at any data point can be certified in a polyhedron that depends on the subspace representation of the point. Using experiments on MNIST dataset, they show that the polyhedron certificate can be complementary to the spherical certificate one can get with randomized smoothing. ", "questions": "- For $\\sigma = 0.04$ (red and green curves) Figure 6 seems to show that the the paper's method gives a worse certificate than randomized smoothing. Is this a typo?\n- Is it possible to find the radius of the largest $\\ell_p$ ball centered at x that fits inside C(x)? This will give a data-dependent spherical certificate at each point, which will be interesting. \n\nMinor suggestions:\n- I think it is better to show the dependence on dimension for the constants $\\epsilon, \\delta$ in the main theorems of sections 2 and 3. \n- The connections of the main theorem of section 4 to subspace clustering literature can probably be presented much earlier. Currently, the paper only brings up this connection at the end of section 4. ", "limitations": "Yes. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Necessary condition: The theorem showing the necessity of concentration for robustness results from a simple, but nice application of the Brunn-Minkowski inequality. I think this condition is novel, and complements existing results showing concentration of measure is bad for robustness\n- Polyhedral certificate: The theorem showing the polyhedral certificate for robustness appears non-trivial and interesting. The certificate obtained is complementary to the spherical certificates of randomized smoothing. \n- Writing: The paper is well-written and clear for the most part. ", "weaknesses": "- Definition 3.1: I think the definition of strongly concentrated distributions is a misnomer. The critical assumption in this definition is in line 125 which assumes minimal overlap between the approximate supports of the class conditional distributions. Hence, this definition has more to do with \"well-separatedness\" of class conditional distributions, and in my opinion, has very little relation to concentration. \n- Novelty of the sufficient condition: If concentration on small volume sets is not sufficient for robustness, what is? As I state in the previous point, it is some notion of separation between class conditional distributions. Several papers already study such conditions. For example, [this](http://proceedings.mlr.press/v119/pydi20a/pydi20a.pdf) and [this](https://proceedings.neurips.cc/paper/2019/file/02bf86214e264535e3412283e817deaa-Paper.pdf) paper show that if the class-conditional distributions are well-separated in an optimal-transport distance, then there exists a robust classifier. It is also shown in these papers that such a separation condition holds empirically on real-world datasets. \n- The low-dimensional linear subspace assumption: First, I think this is a very strong assumption that real world datasets probably don't satisfy. Second, the motivation for studying distributions of this form appears weak, as one can imagine many other types of distributions that satisfy the necessary and sufficient conditions of sections 2 and 3 but are not supported on linear subspaces. Case in point is Example 3.1 in this very paper. \n- The utility of polyhedral certificate: Intuitively, one can imagine many \"benevolent perturbations\" to input data that do not affect the accuracy of a classifier. Spherical certificates for robustness make sense because the guarantee holds for any possible direction of the adversarial perturbation. A polyhedral certificate is not a \"worst-case\" certificate in this sense. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for finding our proof techniques and our polyhedral certificates novel, and the paper well written. We address your questions and concerns below:\n\n> Q2: Is it possible to find the radius of the largest ball around x that fits inside C(x)?\n\nGood question. While a closed form solution is not possible in general, we already provided an optimization problem that obtains this radius in the Appendix F.1. This problem is computationally expensive to solve exactly, and it might be possible to obtain an efficient approximation (like other related work on exact certificates [A]). This is currently mentioned on L345 in the main paper, but we will make it more prominent.\n\n> Q1: Typo in Fig. 6?\n\nThere is no typo, $\\sigma$ is a hyper parameter for RS - our method performs best at $\\sigma = 0.02$, whereas the baseline works best at $\\sigma = 0.04$. As L351 mentions, the differences are really slight between the curves, as the $x$-axis is zoomed in.\n\n---\n\n**On Definition 3.1**\nSec 3 obtains a sufficient condition for the existence of a robust classifier. There are two parts to Def 3.1: the concentration, and the separation parts. The separation condition requires existence of sets $S_i$ such that $q_i(S_j^{2\\epsilon})$ is small for $i \\neq j$. Without further restrictions, the empty sets are trivially separated. The missing ingredient for ensuring robustness is that the measure $q_i(S_i)$ should be large enough. Now both these conditions cannot be true without the volume of $S_i$ being small enough (as the volume of the expansion blows up otherwise): this is precisely our concentration part. Thus, concentration is important for any sufficient condition. In fact, please see the [global response][1] for a detailed discussion on why Def 3.1 is essentially the minimum required for any sufficient condition for robustness. \n\n**Comparison to [1,2]** Our results are complementary to [1,2], and are derived in a more general multi-class setting:\n\nThe theoretical results in [1,2] obtain a nice lower bound in *a binary classification setting* on the adversarial risk $R$ in terms of the wasserstein distance $D$ between the class conditionals $q_0$ and $q_1$, i.e., $R(f, \\epsilon) \\geq 1 - D_\\epsilon(q_0, q_1)$. Our theoretical results Thm 2.1, Thm 3.1 are derived in the multi-class setting, and a priori it is unclear how to extend the results in [1,2] to the multiclass setting. Nevertheless, [1,2] roughly states that the lower bound increases as it becomes more likely to find $x \\sim q_0$, $x' \\sim q_1$ such that $||x - x'|| \\leq 2\\epsilon$, i.e., as the class conditionals get *closer*. In comparison, for two classes, our Theorem 3.1 roughly states that $q_0$, $q_1$ should be concentrated on small subsets $2\\epsilon$ separated from one another. Thus, both our Thm 3.1 and [1, 2] have a similar message, while Thm 3.1 is valid in a more general multi class setting. Finally, note that the *small subsets* part is not explicitly mentioned in [1, 2], but is implicit, as $1 - D_\\epsilon(q_0, q_1)$ is large due to concentration of measure when $q_0,q_1$ do not concentrate on very small subsets.\n\nThe empirical results in [1,2] create an *empirical distribution* $\\hat p$ by selecting *two* classes from real-world datasets (CIFAR-10, Fashion MNIST), which simply places probability mass $1/N$ on each of the $N$ samples in the dataset. [1,2] evaluate their lower bounds on $\\hat p$, and not on the actual real world distribution $p$ -- which might be arbitrarily complex -- and hence we would not say that \"their condition holds empirically for real world datasets\", as the reviewer mentions. In fact, the same experiment can be translated to our setting for any real world dataset, our Thm 3.1 would then show the existence of a robust classifier for $\\hat p$. Just like [1,2] need to solve a discrete optimization problem to evaluate their lower bound on $\\hat p$, we would need to solve a discrete problem for finding the concentrated sets $S$ in Thm 3.1. Even though valid only for $\\hat p$, these analyses are interesting, and have been added to the [global response][1].\n\nThanks for pointing out these references, we will add them to the related work section.\n\n**On Polyhedral Certificates**\nAs the reviewer mentions, for any image $x$ there are some benevolent directions $v$ that do not matter for a human (e.g. changing the background), and other directions that do. Spherical certificates treat every direction as the same, and hence cannot capture the above asymmetry. Polyhedral certificates provide a way to move beyond such restrictions, are a step towards certificates aligned with human perception, in our opinion. Additionally, one can always find the largest ball inside a polyhedron (Q2 above) to obtain a spherical certificate from a polyhedral one.\n\n**On Distributional Assumptions in Sec 4**\nSec. 4 deals with a very specific instantiation of our general theory, for data distributions supported *near* low dimensional linear subspaces, an assumption suited for several real-world tasks including cancer subtyping [B], hyper spectral image segmentation [C] and face recognition. Studying such assumptions is useful, as we are able to obtain novel polyhedral certificates that move beyond the $\\ell_p$ bounds studied in the certified robustness literature. However, any assumption has datasets that might not satisfy it, like CIFAR-10. Nevertheless, our theory can still be used for such datasets, and we provide experiments and thoughts in the [global response][1] showing a possible path.\n\n**Minor Suggestions** Thanks for the suggestions, we will reconsider placement of the connections to subspace clustering literature, and mention the dependence on the constants.\n\n[A]:Wang et.al., Beta-CROWN, NeurIPS 2021\n[B]:McWilliams et.al., Subspace clustering of high-dimensional data\n[C]:Zhang et.al., Spectral–spatial sparse subspace clustering for hyperspectral remote sensing images\n\n[1]: https://openreview.net/forum?id=JDoA6admhv&noteId=hpTXK3MMPW"}]

Author rebuttal:
**Comment to Everybody**
We thank the reviewers for their time and thoughtful reviews. We address broader questions here, and leave the rest to individual responses. At a high level, we have explained the importance of our concentration theorems, their applicability to real world datasets, and their relationship to other work pointed out by the reviewers. On the empirical side, we have conducted new experiments on CIFAR-10, and found that the results (PDF attached) follow trends similar to our original MNIST experiments, providing further validation for our theoretical ideas. We hope to have met all the reviewers' concerns, and look forward to engaging with them during the discussion phase for any further questions.

**Are natural image distributions strongly concentrated?** 
Consider the task of classifying images of dogs vs cats. Any small $\ell_2$ perturbation (say of size $\epsilon = 0.1$) to an image of a dog is not likely to change it to an image of a cat -- the true label (or a human decision) does not change with small perturbations. Let $S_{cat}$ be the set of images that are cats with a high confidence, and similarly for $S_{dog}$. What we just said was that any image in the $\epsilon$-expansion of $S_{cat}$ is not likely to be a dog, and vice versa. This is precisely the condition of separation in the definition of strong concentration: $q_{dog}(S_{cat}^{\epsilon}) \leq \gamma$, and $q_{cat}(S_{dog}^{\epsilon}) \leq \gamma$, for a small $\gamma$. The other condition of concentration is satisfied due to Theorem 2.1 assuming the existence of a robust human classifier.

Now, despite the above, the task of practically classifying an image into a dog or a cat is not trivial at all, as the sets $S_{dog}$ and $S_{cat}$ might be very complex, and hence it might be computationally hard to find a predictor (neural network, or any other classifier) for distinguishing $S_{dog}$ and $S_{cat}$. Using modern deep learning, one is able to learn an approximation to these sets that leads to small standard error, but this approximation is still bad enough that the learned predictor is very susceptible to adversarial examples. This is to say that task of robustly classifying an image into dog or cat is even harder.

**Necessity of Definition 3.1**

In Def 3.1, we are trying to obtain a sufficient condition for the existence of a robust classifier. There are two parts to Def 3.1: the concentration, and the separation conditions. The first is essential, as Theorem 2.1 says that whenever a robust classifier exists for a data distribution, the class conditionals are concentrated (i.e., it is necessary). Hence we discuss the latter:

- Firstly, as we argued above, the separation condition is not strong, and should be satisfied by image distributions like MNIST, CIFAR-10 and ImageNet. 

- Secondly, let us walk through the separation condition to see whether it can be relaxed. As we note at the start of Sec. 3, if all the class conditionals were to be concentrated on subsets $S_i$ that have high intersection among each other, then even benign classification would be hard (i.e., benign risk will be high), let alone robust classification. So, even for the existence of a good benign classifier, it is essential for $S_i \cap S_j$ to be close to empty, for all $i \neq j$. 

    Now, even if $S_i \cap S_j$ were almost empty, for a robust classifier, we care about the $\epsilon$-expansions of these sets to not intersect. In other words, we do not want an $\epsilon$-perturbed cat to look like a dog. Hence, for the existence of a good robust classifier, $S_i \cap S_j^{+\epsilon}$ should be close to empty, for all $i \neq j$. In measure terms, this is same as $q_i(S_j^{+\epsilon}) \leq \gamma$, for a small $\gamma$. Upto this, all these conditions are essential for obtaining a robust classifier.

    Now, note that in Def 3.1, the expansion is taken for $2 \epsilon$, instead of $\epsilon$. This is where our proof technique for Theorem 3.1 incurs a slack of $\epsilon$, and we believe a different approach for constructing the robust classifier might be able to reduce the expansion requirement to $\epsilon$. This could be an interesting avenue for relaxing Definition 3.1 and thereby strengthening Theorem 3.1, and we will add the same to the future work section. 

Thus, even though Defn 3.1 leads to a robust classifier, it is really $\epsilon$-close to the minimum set of assumptions required to guarantee the existence of a robust classifier, and has not appeared in the literature so far, to the best of our knowledge. 

**Experimental Results on CIFAR-10**

We have applied our method to CIFAR-10, and provided experiments in the attached rebuttal PDF. To do this, we first embed each CIFAR-10 image $x$ into a feature space $\phi(x)$, designed such that $\ell_2$-bounded perturbations in the feature space, i.e., $\phi(x) + v$, $||v||_2 \leq \epsilon$, correspond to *semantic* perturbations in the input space, e.g., distorting the image. Such a feature space $\phi$ is obtained following recent popular work in learning perceptual metrics in vision [A], where the task is precisely to learn a feature representation where $\ell_2$ distances align with human perception. We now use our subspace model on $\phi(X)$, and perform exactly the experiments in Sec 5, and make similar observations: we obtain reasonable robust accuracy using our method (Fig 1 blue lines), and this accuracy is maintained within our certified polyhedra at high epsilon, where existing defenses are not robust.

Though such experiments showing feature space certificates have appeared in the literature [B], the question of whether the perceptual representation $\phi$ is itself susceptible to small adversarial perturbations still remains for future exploration.

[A]: Zhang et. al., The Unreasonable Effectiveness of Deep Features as a Perceptual Metric, CVPR 2018
[B]: Voracek et. al., Provably Adversarially Robust Nearest Prototype Classifiers, ICML 2022

Meta-review: It's nice that a somewhat implicit intuition for when adversarial examples exist has been formalized a bit more. As reviewers noted, it's unclear how practically useful the suggested certification is, as there is an issue about comparability (which the authors definitely try to address as well as possible), but the theoretical results are interesting enough even without the experiments. The writing is clear. We ask the authors to address the reviewer's suggestions in the camera-ready and perhaps in the related work section consider pointing to some more references that argue based on a similar intuition - in addition to the mentioned papers, that's e.g. the role of the margin in PAC-Bayes robust generalization bounds as in Farnia et al '18, Xiao et al. '23 and the notion of consistent perturbations as in standard vs. adversarial accuracy tradeoff paper as in Raghunathan et al. '19).
Decision: Accept (poster)