Fundamental limits on the robustness of image classifiers
Authors: Zheng Dai
David Gifford
Venue: ICLR 2023 poster (2023)
Keywords: Theory
Computer vision
Isoperimetry

Abstract: We prove that image classifiers are fundamentally sensitive to small perturbations in their inputs. Specifically, we show that given some image space of $n$-by-$n$ images, all but a tiny fraction of images in any image class induced over that space can be moved outside that class by adding some perturbation whose $p$-norm is $O(n^{1/\max{(p,1)}})$, as long as that image class takes up at most half of the image space. We then show that $O(n^{1/\max{(p,1)}})$ is asymptotically optimal. Finally, we show that an increase in the bit depth of the image space leads to a loss in robustness. We supplement our results with a discussion of their implications for vision systems.

Published as a conference paper at ICLR 2023
FUNDAMENTAL LIMITS ON THE ROBUSTNESS OF IMAGE CLASSIFIERS
Zheng Dai & David K. Gifford Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology
Cambridge, MA 02139, USA (zhengdai, gi fford] @mit edu
ABSTRACT
We prove that image classifiers are fundamentally sensitive to small perturbations in their inputs. Specifically, we show that given some image space of n-by-n images, all but a tiny fraction of images in any image class induced over that space can be moved outside that class by adding some perturbation whose p-norm is On max (p.1)), as long that image class takes up most half of the image space. We then show that (n max (p.1)) is asymptotically optimal. Finally, we show that an increase in the bit depth of the image space leads to a loss in robustness. We supplement our results with a discussion of their implications for vision systems.
INTRODUCTION
Image classification, the task of partitioning images into various classes, is classical problem in computer science with countless practical applications. Progress on this problem has advanced with leaps and bounds since the advent of deep learning, with modern image classifiers attaining some incredible results(Beyen et al. 2020). However, has been observed that image classes tend to be brittle- classifiers like to partition images in way such that most images lie very close to images of different classes (Szegedy et al. 2013). Although usually studied computer vision systems, such phenomena also appear manifest in natural vision systems systems<Elsayed et al. 2018 Zhou & Firestone 2019).
Given these observations, it is natural to ask the following question: is the brittleness of image classes a result of classifier construction, or does it arise from some fundamental property of image spaces? Previous work demonstrate that classifiers can be made more robust function of how they constructed, and attempts to improve the robustness of existing computer vision systems through such means is active
of research research(Moosavi-DDeeres Moosavi-Deztooll et al. 2016 Madry et al. 2017]] Ma et al.,
2018 Tramer et al.) 2020 Machado et al.) 2021). However, there is also fundamental limit to the robustness achievable by any classifier that arises a consequence of the geometry of image spaces.
In this work we show that this fundamental limit of achievable robustness is surprisingly low. Roughly speaking, in most cases it suffices to change the contents of only few columns of pixels in an image to change its class. Even smaller changes are sufficient when measured using other metrics, such as the Fuclidean metric. Our results are consequence of the geometry image spaces, and so they apply regardless of the architecture of the classifier. This suggests that there is an inherent brittleness in the semantic content of images, and that robustness as an objective is only desirable with respect to distributions that are concentrated over small subsets of the image space.
1.1 OUR CONTRIBUTIONS AND RELATED WORK
The observation that image classes tend to be brittle was popularized by Szegedy et al. (2013), where it was observed that tiny perturbations suffice to change the image class of many images. This has since opened up a rich field research on how the brittleness of image classes arise from specific classifier formulations training distributions (Goodfellow al. 2014 Gilmer al.) 2018 Tsipras

---

Published as a conference paper at ICLR 2023
While these advances offer insights into the deficiencies of our current methodologies, their analyses ultimately depend on some aspect of the architecture or training distribution, so do not rule out the possible existence of ideal classifiers that do not induce brittle image classes.
al. 2018
By contrast, our work provides a non-trivial upper bound to the robustness of any image class" Specifically:
We prove that most images in any image class consisting of at most half the images in an image space of n- n-by-n images can be moved into a different class by adding perturbation whose p-norm is On+ max (). This is a vanishingly small quantity in relation to the average distances in the image space, which is (n max ()) and therefore provides a non-trivial upper bound for the robustness attainable by even ideal classifier.
We show that there exist image classes where most images cannot be moved into a different class with any perturbation whose p-norm is o(n 1/ max (v)1)) (note the small-o notation Therefore, the bound we derive is asymptotically optimal in n, so proving stronger robustness bounds will require examining classifier-specifie properties.
We show that discretization through lowering the bit depth of the image space permits the existence of more robust image classes. This lends theoretical backing to the idea of using discretization method of defending against adversarial attacks (Panda et al. 2019).
We demonstrate that brittle features in images can deliver semantic content. We argue that deeper understanding of such features can lead to advances in aligning human and computer vision systems.
To our knowledge, there are two previous works that investigate upper bounds of robustness that arise from the geometry of image spaces. One is from Fawzi et al. (2018a). which provides an upper bound for the probability that an image drawn from a given distribution is far from images a different class. They further perform numerical experimental analyses of their bounds. However, our analysis differs and improves on theirs in a few key aspects. Firstly, they only analyze the case where distance is measured using the 2-norm, while provide bounds for p-norms for any p. Secondly, they do not account for the discrete nature of image spaces with finite bit depth, which allows for Finally, their bound is parametrized by
classifiers that are more robust than their bounds imply" d modulus of continuity which differs depending on the image distribution, potentially resulting in trivial bounds for certain distributions. Furthermore, this parameter cannot be computed exactly, so in application their bound is inexact. By contrast, we formulate our results independently of specific image distribution Our bounds can therefore computed exactly and unconditionally. and we are able to show the asymptotic optimality of our result.
The other work is from Diochnos et al. (2018), which investigates partitions of bit vectors. Since bit vectors can be used to encode discrete inputs, their results can be viewed as results about classifiers over discrete inputs. They also view each bit vector as being equally weighted, so their results are not parametrized by data distributions and are unambiguous. They show that given finite probability of misclassification, an arbitrarily high proportion vectors can be turned into misclassified vectors through small numbers of bit flips proportional to the square root of the vector dimension. This result has been generalized in follow-up work (Mahloujifar et al., 2019). where it was shown that a small number of modifications proportional the square root of the data dimension suffices induce misclassification in the more general setting of Lévy families as well. However, these results are still dependent on the existence of finite fraction of misclassified datapoints, and therefore do not preclude the existence of asymptotically infinitesimal image classes that are robust, something which
Goodfellow et al. (2014) demonstrate how lincarity can allow imperceptible changes across a large amount of dimensions to accumulate to something significant, Gilmer et al. (2018) derive a relation between classification error rate and the distance to the closest misclassification on a specific dataset of concentric spheres, and Tsipras
et al. (2018) derive fundamental tradeoff' between accuracy and robustness.
Consisting of at most half the images the image space.
fn)) O(g(n)) + lim timsup,_.. wix)
f(n) < oc and f(n) E o(g(n)) + lim
f(n)
g(#)
*Other work, such as that of Diochnos et al. (2018), does analyze discrete input spaces, but does investigate the relation between discretization and robustness.
'I is still possihle adapt our result to account for image distribution using their techniques. See our discussion for additional details.
2

---

Published as a conference paper at ICLR 2023
analysis does preclude. Furthermore bounds, due to our focus image spaces, much stronger than the ones they derive and are asymptotically optimal.
The observation that brittle features deliver semantic content is observation on the inadequacy of p-norms for quantifying visual similarity. While such inadequacies have been noted in prior work (Tramer et al. 2020 Fawzi et al.. (0188), to our knowledge ours is the first that have been derived as a consequence of theoretical bounds. The theoretical foundation of our observations allows for quantification and has the potential imply further consequences.
RESULTS
2.1 PRELIMINARIES
Images consist of pixels (for example R, G, and B) of varying intensity. We therefore define the image space of h-channel images of height n and aspect ratio q. denoted (n.e.. as the set of all real valued tensors with shape (qn, n, h) with entries lying in the interval [0, 1]. We require that gn be an intege The first two dimensions index the x and y coordinate of the pixel, while the third indexes the channel.
dimensional grid, with each pixel consisting of set of channels
Only a finite subset of these images can be represented with finite bit strings. Therefore, we use (o. to denote the subset of hooo. where each entry in the tensor is one 2' equally spaced values between and inclusive (in other words, each entry belongs to [0, 1] (i/(2) 1)li Z)). We will refer to as the bit depth of the image space. Although technically image spaces of equal height, aspect ratio, and number of channels intersect, we will treat them as disjoint (in other words, if x E (b). then & In',g', ((C if (b) # In' ((,,),)))))
Images in the image space (()) contain n² qh entries. This quantity n n²qhh appears often in our results and can be thought of as the data dimension (the number of dimensions required to specify the data), which we will often denote with N for simplicity. The data dimension can be set to any integer value (for example by setting = 1 and q 1), any data type that can be represented as Cartesian product of some fixed number unit intervals [o, 1] can be viewed as an image as we have defined it. Consequently our theoretical results be applied to more general class of inputs than images, though we will continue to focus on the case of image classification this work.
2.1.1 CLASSIFIERS AND CLASSES
classifier a function In.g.h.(8) + V, where y is some finite set of labels. For each y E V, we define the class of y as the preimage of y. denoted as the set of images C Cy) We say that such class is induced by C. If a class takes up a large part of the image space, then it contains lot of images that look like randomly sampled noise, since randomly sampling channel values from a the image space. Therefore, many images in
uniform distribution yields uniform distribution these classes tend to be uninteresting, which motivates the following definition:
Definition 1. A set C C In.g.h.(M)) is an interesting image class if it is not empry, and if it contains no more than half of the total number of images in In...h(bb)-
Note that as long every class of a classifier is populated, more than one class can be uninteresting since image classes are disjoint. Therefore, if classifier does induce an uninteresting class, we can think of as the uninteresting class. Intuitively we can think of it as a junk class, since it contains images that look like randomly sampled noise.
Most of our results will pertain to interesting image classes. This is to eliminate pathological considerations such as when an image class covers the entire image space.
'We opt to use qn rather than a separate value for image width to suggest that the height and width of an image should have similar magnitudes. "Tii because our results depend only on the size of the image tensor rather than its shape.
3

---

Published as a conference paper at ICLR 2023
2.1.2 PERTURBATIONS AND ROBUSTNESS
In order discuss perturbations, we define addition and subtraction over tensors that are of the same shape to be element-wise, and we define the p-norm of tensor A, denoted || to be the pth root of the sum of the absolute values of the entries of A raised to the pth power. p assumed to be non-negative integer, and for the special case of p = 0 we let ||.4llo be the number of non-zero entries in Note that when p is the O-"norm" is not truly norm since it does not obey homogeneity.
We can then define what it means for an image to be robust to perturbations:
Definition 2. Let S In.g.h((b) be a class of images. We say an image I is robust to T JP-perturbations of size for all I' E In.gh.()), | 1l S d implies I' E C.
We can then define what it means for class to be robust to perturbations. Note that unless class occupies the entire image space, must contain some non-robust images, so the best we can hope for is attain robustness for a large fraction of the images within class. This is reflected in the following definition.
Definition 3.
Let C In), be class of images. Then we say that C is r-robust LP- perturbations of size d if it is not empry, and the number of images I E C that are robust to L 1P-perturbations of size is at least r(C), where |C] is the number of images in C.
2.2
UNIVERSAL UPPER BOUND ON CLASSIFIER ROBUSTNESS
We now state universal non-robustness result that applies all classifiers over discrete image spaces (b))
Theorem 1. For all real values c > there exists no interesting class C In.ghh(()) (the image space of h-channel images of height and aspect ratio q with bit depth b) that is 2e 2c. -robust to L Pe-perturbations size
size (2 + cv // where N =n²gh is the data dimension.
max(p.1),
Proof sketch. We can use the images in In.g.h.(8) to form a graph where images are the vertices, and images are connected if and only if they differ at exactly channel. In other words, the image tensors must differ at precisely one entry. Figure illustrates the construction of this graph. Note that graph distance between vertices coincides with the Hamming distance between the images represented by the vertices. Such graphs are known as Hamming graphs, and they have a vertex expansion (or isoperimetry) property (Harper) 1999) which implies that for any sufficiently small set, if we add all vertices that are within graph distance of O(vN) that set, then the size of that set increases by at least some given factor (see Figure Mp for an example). This expansion property contingent on the size of the vertex set being sufficiently small, which is why we require the "interesting class" property.
We can then show that an interesting class cannot be too robust the following way: suppose for contradiction that it is. Then there must be some set C' C C' that is pretty large, and has the property that all vertices within some graph distance of C' are C. We can then use the vertex expansion property to show that adding these vertices to C' gives set larger than C, which contradicts the assumption that all vertices within some graph distance to C" are C. Plugging explicit values into this argument yields the statement of the theorem.
We can then generalize to L LP-perturbations for arbitrary p since each coordinate varies by at most unit. The full proof can be found in Appendix A.I
Intuitively, the above results state that to change the class of most "interesting" images, the number of pixels that need to be changed is roughly the number contained in a few columns of the image.
2.2.1 THE UNIVERSAL NON- ROBUSTNESS RESULTS ARE ASYMPTOTICALLY OPTIMAL UP TO A CONSTANT FACTOR
Up to a constant factor, the bounds in Theorem I are the best possible for a universal non-robustness result that applies arbitrary predictors if we only consider the data dimension N and hold the bit depth b constant. In other words, there exists no bound on robustness that applies universally to all classifiers that grows much more slowly in N than the ones given in Theorem T Therefore, if we wish
4

---

Published as a conference paper at ICLR 2023
Exzanatin
a)
b)
Interpreting image spaces as Hamming graphs We show how construct a Hamming graph using the elements of 12), the space of binary images on four pixels. By construction, graph distance coincides exactly with Hamming distance. b) We demonstrate the expansion property Hamming graphs on Hamming graph constructed using (,1), as the vertex set. If we pick some initial set of vertices (in black), then the set of vertices that are graph distance set (in black and red) is much larger than that initial set. The nature of "much larger" is expanded on in Appendix A.I
Figure I:
most 3 (3 being the image height n in this case) from that initial
to show that the classes induced by some classifier are not robust to, for instance, L pertturbattinns of size (lo)(())) more specific properties of that classifier would need to be considered.
To prove this, consider the classifier defined by Algorithm
Algorithm I: Robust Classifier
Input: :An image E (..).
Result:
A label belonging {0, 1}
S 5 0;
for x 1 to qn do
for y + to n do
for a 1 to do
S - S I y.
S < n22 then return 0;
else
return 1;
Theorem 2. The classifier described by Algorithm induces an interesting class C C ( (the image space of h-channel images of height and aspect ratio with bit depth b) such that for all > 0:
1. C. -ccc-robuust to LP -e-perturbations of size c/N - for all S 1.
(c/N-2)M/>
2. C is (1 4c)-robust L -e-perturaations of size (2 1111-11-177 for all p > 2.
Where N n² qh is the data dimension.
Proof sketch. Given an image I, let S(I) be the sum of all its channel values subtracted by N/2 (where N = nh is the data dimension). Then being robust to L'--erturbatiios of size ær is approximately equivalent to S(I) & [-r,x]. By the central limit theorem, the fraction of images such that S(T) & [-evN, eVN] is some monotonic function of c. independent of N if N is sufficiently large, which is our desired result. Appendix A.2 A.2 provides more careful analysis of this that does not rely on limiting behaviour and extends the result to all p-norms.
In Einstein notation, the algorithm returns Tz. 1 F.v.a n22hh/2 on image tensor 1, where 1 is shaped like and has 1 each entry. We spell out the algorithm in pseudocade for clarity.
5

---

to Published as a conference paper at ICLR 2023
We remark that the in Theorem 2 statement.
should be set less than 1/4 in order to yield non-trivial
2.2.2 CLASSIFIER ROBUSTNESS TO L D'-PERTURBATIONS DECREASES WITH INCREASING BIT DEPTH FOR p p 2
In this section we investigate the role played by the bit depth b. Theorem has a dependency on b when considering jf-perturbations for p 2 2. the statement about attainable robustness becomes increasingly vacuous as the bit depth increases. Somewhat surprisingly, this is not an artifact of suboptimal analysis: it is really the case that the fundamental limits of robustness drops as function of the bit depth of the image space.
Theorem 3. For all real values > and p 2 2, no interesting class C In.g.h.(b) (the image space of h-channel images of height n and aspect ratio q with bit depth b) is 2e
L ---perturbations of size 2c+ 2/N 2/p where N = n² n² is the data dimension.
Proof sketch. We will focus on the 2-norm. Extension higher p-norms is straightforward and is given as part of the full proof found in Appendix A..3 The main idea of the proof rests on the fact that if we extend the classifier the continuous image space with something like nearest neighbour approach, the measure of the images that are robust to perturbations of constant size is small (the statement and proof may be found in Appendix [A.4). Therefore. we randomly jump from an image in the discrete image space to an image in the continuous image space, with high probability we will be within a constant distance of an image a different class. The size of this random jump can be controlled with factor that shrinks with increasing bit depth. Summing up the budget required for this jump, the perturbation required on the continuous image space, and the jump back to the discrete image space yields the desired bound.
We remark that this suggests that the bounds in Theorem | pertaining to IP-perturbations for 2 2 can be improved to reflect its dependency on the bit depth b. However, whether the component that shrinks with b scales with 11/2p rather than ///P remains open problem.
3 DISCUSSION
3.1 SUMMARY OF ROBUSTNESS LIMITS AND THEIR RELATION TO AVERAGE IMAGE DISTANCES
We summarize the bounds we derived in the previous section in Table T where the bounds are reparametrized in terms of the robustness. An asymptotic bound is also provided with respect to the data dimension and bit depth A plot of the relation between perturbation sizes and robustness can be found in Appendix A.6
With respect to N and b, the bounds derived for the 0-norm and 1-norm are asymptotically optimal, while the bounds for the other p-norms are asymptotically optimal with respect to N. Finding the optimal bound with respect to both and N for p-norms for p 2 remains an open problem, although our current analysis suffices to show that b does fundamentally influence how robust an interesting class can be.
We note that the bounds we derived are vanishingly small when compared typical distances between random elements of the image space. a pair of images I, I E (m.g. are sampled independently and uniformly, we have:
B T r''p]) 2 ko.p / max(1.p)
Where ko.p is some constant parametrized by b and p, and = gh is the data dimension. See Appendix for additional details. While our analysis there does not necessarily hold for images drawn non uniformly, we demonstrate in Appendii(A...II tend to be similar in size.
A.5. that typical distances on natural distributions
When this observation is combined with the bounds in Table I we can see that when N sufficiently large, for 99% (or some arbitrarily high percentage) of images 7" within an interesting class C:

---

Published as a conference paper at ICLR 2023
Table 1: Fundamental bounds for robustness attainable by any interesting image class in (b))
N n² is the data dimension. Rather than leaving the robustness and bound parametrized by separate constant the bounds have been reparametrized in terms of the robustness r. Figures plotting the relation between the bounds and r can be found in Appendix [A.6] The bounds are also given in big-Q notation, where r is held constant for simplicity. The upper bound should be understood as "no interesting class r-robust to perturbations of these sizes" and the lower bound should be interpreted "there exists interesting class that is r-robust to perturbations of these sizes".
PERTURBATION
UPPER BOUND
LOWER BOUND
L PERTURBATION
I -PERTURRATION
+
V IimLENT
-2 (--))-
min (2+ V (2in( 2 (NNN 1/2
-24 2+ ( ( 1/2
L"- -PERTURBATION, 222
(22ml 20-1 VN)2/0)
(2 1) 13/8
PERTURBATION
UPPER BOUND
LOWER BOUND
- PERTURBATION
L' PERTURBATION
@(VN)
@(VN)
L JP-PERTURBATION, p 223 2
VN
O /2p
+ Ommin(N1/22
+ 1)2p/)
26
20((p-1)/p)
minxez, aa 111"
X1lp
S Cb.p 2maxlp,1]
Eill - Plpp]]
Where Cb.p is some constant parametrized by b and p.
The right hand side approaches as N grows without bound, so compared to typical distances one finds an image space, the distance of image an image outside of its class is vanishingly small in any p-norm it is measured in.
3.2 IMPLICATIONS OF ROBUSTNESS LIMITS FOR COMPUTER VISION SYSTEMS
According to our results, a large fraction of images in any interesting image class are can have their classes modified by small perturbation. We note that we only consider the case of image classifiers that partition images into finite number of discrete classes, so our results do not apply directly to vision models that output class probabilities or some more abstract representation. However, these outputs must ultimately be converted into decisions when the model is deployed, at which point our bounds do apply.
Taken at face value, our results appear to pose barrier for the construction of reliable computer vision systems. For illustration, suppose we implement a system that selects from finite pool of actions to take depending on the output of some image classifier. Then for most images, tiny perturbation can make the given image trigger undesired behaviour, ostensibly making the classifier unreliable.
One way of circumventing this barrier to consider reliability conditioned on a prespecified image distribution. Our bounds do not immediately preclude the existence of small fractions of images within interesting image classes that are robust to large perturbations, and is possible that those are precisely the set of images that commonly encountered in deployment. Therefore, our bounds do not directly prevent the construction of classifiers that are robust with respect to some given image distribution, which is an ongoing field of (nearch(MMadry et al. 2017.
7

---

Published as a conference paper at ICLR 2023
We remark that our bounds can be converted into bounds that take image distribution into account through tricks similar to ones used by Fawzi et al. (2018a). We can define a map f h...g.h.(bb - (.,0. such that f(X) approximates the desired image distribution X is distributed uniformly over (b. (we can think of the preimage as some latent space). If we then define a monotonically increasing w : IR + R such that [x) f(x')lpp I w[|| x'Ilp) for all pairs of images, then all our bounds stating that no interesting class is r-robust to IP-perturbations of size d can be converted into statements about how the probability of encountering an image in an interesting class that is robust to L p--petuurbation of size w(d) is less than r. Clearly the value of such a bound necessarily depends on ff and w, and it is easy construct examples where these bounds must be vacuous- for example, we could make f map all images of one class to the entirely black image and all images of the other class the entirely white image. However, this is unrealistic toy example, and experimental analysis carried out by Fawzi et al.] (2018a) suggest that analyzing plausible approximations of f that produce useful distributions can produce informative bounds.
However, we also note that formulating robustness in a distribution specific way does not address all reliability concerns: for example, an ostensibly benign image modified imperceptibly to trigger dangerous behaviour can be a reliability concern regardless of whether said image is drawn from a prespecified distribution. Furthermore, identifying the correct distribution of such images is a non-trivial task, and distribution gaps can lead to significant reductions in performance((Rcct et al. 2019).
Another way of circumventing the barrier to constructing reliable computer vision systems imposed by our bounds is to note that perturbation with a small p-norm not necessarily imperceptible. In these cases, the classifier ought to adjust its output with respect to such perturbations. Robustness should then be defined with respect to perception aligned metric, as opposed to with some p-norm. The barrier constructing reliable computer vision systems then becomes the alignment problem for human and computer vision systems.
3.3 BRITTLE FEATURES CAN IMPART SEMANTICALLY SALIENT INFORMATION
We show in this section that the semantic contents of most images are contained within brittle features that can be erased with a small perturbation. First, we note that our bounds apply universally to any image classifier, so they must apply to an ideal classifier that is able to faithfully mimic human classifications. Although such a classifier has yet to be achieved in the computer vision space, human based classifiers can be built quite easily: simply place people in front monitors and ask them to apply labels to images"] Memoization could be applied to prevent the same image from being classified multiple times with conflicting labels. This system, on top of producing human classifications, acts like a classifier which partitions the set of all images into disjoint classes (as described in Section 2.1.1. therefore our bounds must be satisfied 10
At this point, we have proven the existence of a classifier that reproduces human classifications. To simplify the discussion, we will consider classifiers with only two classes: given a set of word we will consider the class of images that such label can be applied and its complement. Specifically, the words should be chosen in a way such that random noise should not receive a label with high probability. Roughly speaking, the idea we attempt to capture here that the first class is the class of "meaningful" images, and the latter is the class of "meaningless" images.
Since images drawn from random noise should not receive a label with high probability. the class of meaningless images is far larger than the class of meaningful images. Therefore, the class of meaningful images is an interesting class, and all our bounds apply. This has the surprising consequence that the semantic content of most images can be "erased" with small perturbation by turning them into meaningless images. Put differently, the semantic contents of most meaningful images contained in brittle features that can be erased with small perturbation, which is what we set out to show.
SSuc constructions have heen commercially implemented for purposes like content moderation. 10 may be the case that pair of counterfactual trajectories of classifications would yield contradictory labels on certain images. However, since only one such trajectory can occur factually, memoization suffices to make such a classifier observationally indistinguishable from the kind of classifiers discussed in Section 2.1.1 For example, words like "truck" or "parachute".
8

---

Published as a conference paper at ICLR 2023
b)
Figure 2: Small perturbations can be semantically salient
small perturbation (a) when applied to a uniformly randomly drawn image (b) can add meaning to it (c). Conversely the meaning present in (c) can be removed with a small perturbation to attain (b).
Such a perturbation can also add information to natural image (d. e) - although the information present in the natural image largely remains after applying the perturbation, new information was still added by the perturbation.
"Sourced from from (oward
What do these features look like? A possible example of brittle features that convey semantic information is line drawings (see Figure 2 Line drawings can be erased with perturbation of size (nn (proportional to the height of the image) when measured using the 1-norm or O-norm, which is congruent with the bounds we derived for those metrics. Line drawings are also semantically salient. However, the size of line drawing is generally larger than ((1) when measured with a p-norm with p 2, the saliency of line drawings do not necessarily account for our bit depth dependent bounds. Phenomena like optical illusions and pareidolia may offer some hints as to how saliency can be present in even more brittle features. Some past work highlight other possible ideas, such as the object of interest only taking up a small portion of the picture (Tramèr et al.) (2020). or salient patterns being drawn with low opacity (Fawzi al. 2018b). However, a full understanding remains elusive.
Understanding the ways in which brittle features can carry semantic meaning is not merely of academic curiosity. We have shown that the robustmess of computer vision systems have fundamental limits. However, computer vision system that is aligned to the human visual system ought to obey these limits, since human based classifier must do so as well. Over the past decade we have learned that standard machine learning methodology does not automatically produce vision systems that are aligned to the human visual system with respect to small perturbations (Szegedy et al. 22033), and methodologies that seek to produce such vision systems still contain misalignments (Tramer et al.) 2020). A deeper understanding of how semantic content is conveyed in brittle features may inform the development of future methodologies (for example we may wish to explicitly train computer vision systems on such features), which is becoming increasingly necessary as computer vision systems become increasingly deployed in safety and security critical applications, where the trustworthiness of the system is essential (Pereira & Thomas 2020
Ma et al. 2018).
4 CONCLUSION
We have derived universal non-robustness bounds that apply to any arbitrary image classifier. We have further demonstrated that up to constant factor, these are the best bounds attainable with respect to the dimensions of the image. These bounds provide fundamental limits to the robustness achievable by computer vision systems, and reveal that most images in any interesting class, even those induced by ideal classifiers, can have their class changed with a perturbation that is asymptotically infinitesimal when compared the average distance between images. We then discuss the barriers to constructing safe and secure computer vision systems imposed by our results and how these barriers may be circumvented. Finally, we show the abundance of brittle features that convey semantic information, and propose that an improved understanding of these features may yield progress on the problem of aligning human and computer vision systems. We discuss line drawings as an attractive candidate for brittle features that are semantically salient. However, they are not sufficiently brittle to account for all our bounds, so a full understanding of these features remains the subject of future work.
REPRODUCIBILITY STATEMENT
Complete proofs for claims can be found in the appendix.

---

Published as a conference paper at ICLR 2023
6 ACKNOWLEDGEMENT
This work was supported in part by Schmidt Futures.
REFERENCES
Franck Barthe and Bernard Maurey. Some remarks isoperimetry of gaussian type. In Annales de I'Institut Henri Poincare (B) Probability and Statistics, volume 36, pp. Elsevier, 2000.
Lucas Beyer, Olivier Hénaff, Alexander Kolesnikov, Xiaohua Zhai, and Aäron van den Oord. Are we done with imagenet? arXiv preprint vrXiv:2006.07159 2020.
Dimitrios I Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarial risk and robustness: General definitions and implications for the uniform distribution. arXiv preprint 122.://8 2018.
Gamaleldin F Elsayed, Shreya Shankar, Brian Cheung, Nicolas Papernot, Alex Kurakin, Ian Good- fellow, and Jascha Sohl-Dickstein. Adversarial examples that fool both computer vision and time-limited humans. arXiv preprint arXiv: 2018.
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. arXiv preprint 1rXiv:1802. 100.0080..00066, 2018a.
Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Analysis of classifiers' robustness to adversarial perturbations. Machine learning, 107(3):481500) 2018b.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow. Adversarial spheres. arXiv preprint arXiv:1801.02277, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.66:: 2014.
LH Harper. On an isoperimetric problem for hamming graphs. Discrete applied mathematics, 95 (1-3):285-309, 1999.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pp. 4206. Springer, 1994.
Jeremy Howard. imagenette. URL https: httpp:://aattub.ccoaaaaaaaaaaaaa
Rob Kaas and Jan Buhrman. Mean, median and mode binomial distributions. Neerlandica, 34(1):13-18, 1980.
Statistica
Lei Ma, Felix Juefei-Xu, Minhui Xue, Qiang Hu, Sen Chen, Bo Li, Yang Liu, Jianjun Zhao, Jianxiong Yin, and Simon See. Secure deep learning engineering: A software quality assurance perspective. arXiv preprint 18Xiv:
2018
Gabriel Resende Machado, Eugênio Silva, and Ronaldo Ribeiro Goldschmidt. Adversarial machine learning image classification: A survey toward the defender's perspective. ACM Computing Surveys (CSUR), 55(1):1-38, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: arXiv:1706.006 170.06608, 2017.
Saeed Mahloujifar, Dimitrios Diochnos, and Mohammad Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4536-4543, 2019.
Seyed- Soyee-Mohsen Moosavi-Dezfoolii, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582, 2016.
10

---

Published as a conference paper at ICLR 2023
Priyadarshini Panda, Indranil Chakraborty, and Kaushik Roy. Discretization based solutions for secure machine learning against adversarial attacks. IEEE Access, 7:70157-70168, 2019.
Ana Pereira and Carsten Thomas. Challenges of machine learning applied to safety-critical cyber- physical systems. Machine Learning and Knowledge Extraction, 2(4))579-602 2020.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize imagenet? In International Conference on Machine Learning, pp. 5389-5400. PMIR, 2019.
Herbert Robbins. A remark on stirling's formula. The American mathematical monthly, 62(1):26-25 1955.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jörn-Henrik Jacobsen, Fun- damental tradeoff's between invariance and sensitivity to adversarial perturbations. International Conference on Machine Learning, 9561-9571. PMLR, 2020.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint wxXiv:2002.08347, 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Tumer, and Aleksander Madry. Robustmess may be at odds with accuracy. arXiv preprint arXiv: 1805 12152, 2018.
Zhenglong Zhou and Chaz Firestone. Humans can decipher adversarial images. Nature communica- tions, 10(1):1-9, 2019.
A APPENDIX
A.1 PROOF OF THEOREM
I
A.1.1 PROPERTIES OF BINOMIAL COEFFICIENTS
We will work with binomial coefficients extensively. To simplify some of our statements, we will extend the definition of a binomial coefficient work with any and arbitrary integer
n!
if k
=
kl k))
(3)
otherwise
Binomial coefficients can bound in the following way:
2n when 1.
Lemma 1. (
Proof. We first that n! is bounded by the following for all 2 (Robbins 1955):
n
m!
Vn n
Vn
2/(22n)
2
Applying the appropriate inequalities for the numerator and denominator yields the following for when n is even:
n!!
2D (1(2)))
2
n2/2)
(nn22)1²²
Vn
2
11

---

Published as a conference paper at ICLR 2023
When is odd, we have:
(7)
n2 k
-
(6)
|1//11
n n
(n 1)/2/
2 e2/(12(n+1))
2
(8)
vn +1
2nT
2 e2/(12n)
2
Vn 22T
Where the third comparison is an application of Equation
1/(12m)
If n 2 1, we have
0.5, which proves the claim.
22
It will also be useful to define the following cumulative sums (which are also the tails of binomial distributions):
(k, Ei (1) p)- if 2 0
(10)
otherwise
We show that the ratio of these cumulative monotonic increasing:
Lemma 2. Let E 1). Then (n-((=-)) is monotonic increasing in where 0 S x S n and l: is any positive integer.
(n,(())
Proof. First, we note that the ratio " / is monotonic increasing in x when 0. This holds by definition if x k < O. Otherwise, have the following:
(HW)/C) ( (n (n- x + k)
(n-x) x)
(x k +1)
*
S
(LI)
(x 1
We then claim the following holds for x where 0 S x n 1:
Un.(æ - k)) (n.(() Unp (xr 1)
Unp(I - k ++1)
(x- ( )1 p)
(12)
a+ p
The above holds with equality when x - k + < 1f = 0, the above also holds: the leftmost ratio is O. For the other two ratios, if we multiply the rightmost ratio by - p)n-k above we can see that the numerators are equal while the denominator of the rightmost ratio is smaller. We can prove the other cases by induction on a:
Unplx-10 - k)) Unp(z)
(1)) p)* p"
<
(13)
x b+ ) (1 p)
(14)
1+ 1x
n 1+1 p" x+ (1 -
(15)
p 1 (1 p) ----11
12

---

Published as a conference paper at ICLR 2023
Where the first inequality follows by induction, and the second inequality follows because (,*1/(() is monotonic increasing in
For any positive numbers a, and strictly positive numbers b, d, where S å. we have e S because:
b+d S å
atc
a Ac
bc ad
(b + Xd)a 20
(16)
d
b + Ad
Therefore, we have:
Un -k) k)
(2)(2))
Un(x k)) + 1--41110
kt1 (1 )
(17)
Un.p(x) (+ 1r+ p---1-1
Unp(: 1+
(18)
Un 1)
(1- (1 2))
(19)
As claimed. Carrying the induction up to 1 yields the statement.
A.1.2 BOUNDING THE INTERIOR OF A SET OVER A HAMMING GRAPH
We will prove our main results by application of isoperimetry bounds over Hamming graph. Let W be a set w symbols. Then we define the n dimensional Hamming graph over w letters, denoted H(n, w), the graph with vertex set W and edge set containing all edges between vertices that differ at precisely one coordinate. For example. Hn, 2) is isomorphic to the Boolean hypercube. We will use (H,,n, w)) to denote the vertex set of the Hamming graph.
Let S S H(n, w). We define the expansion of denoted ExP(S), as the set of vertices that are iterate
either in S or have neighbour in S. Since ExP(-) inputs and outputs sets of vertices, it. We will use Exp*(.) denote l: applications of ExP(.).
We now adapt a a result from (Harper 1999) (Theorem 3 in the paper). Additional details on how has been adapted can be found in Appendix B.1 B.I
Lemma (Isoperimetric Theorem on Hamming graphs). Let S & H(n, w). Then:
ExPx (S)
2 min(Un,,( + k)
(H w))l
[S]
(nn,(r) = [V(H(,, w))l pe (0, E [0, - k))
(20)
To work with this we first obtain bounds for the expression on the right hand side of Lemma 3
Lemma 4. Let p be any value in (0, Let 2 k such that (r) 4. Then (r-(r-
(ap((r)
2e (fmax(k-1100)) /mp
Proof. Let X be binomially distributed random variable with trials and probability of success p. Let m be the median X. We have m & np + because the median and mean differ by at most (Kaas & Buhrman 1980).
k) can be interpreted as Pr(X < m - A:), We can then apply Hoeffding's inequality Ho effding 1994)
U Un
13

---

Published as a conference paper at ICLR 2023
Pr(X S m - k) < Pr(X & np + k) -
(21)
(22)
Since m is the median of X, we also have (m)) 2 }. Combining this with the above equation gives:
Un.(mm - k) Un.((m) < 2e 2(max((--100))
(23)
this also implies that the above Since Un.(a=k) is monotonically increasing in æ via Lemma 2 (n)
relation holds for all r < m. This completes the proof.
We can then plug this into Lemma 3 to obtain non-robustness result Hamming graphs, which will then apply to image spaces.
Theorem 4. Let S & VVH(n, w)) such that |S| S [V(H(nn w)) and c > be any number. Let S' C S be the set of vertices for which no path with cynn + edges or less leads to a vertex not in S. -6"
S8 [
Then
Proof. Suppose for contradiction that |S"| 2 2e 2e-2c*1S). Since for any vertex in S" no path with
c/T + 2 edges less leads to vertex outside of S, we have Expeva+2 S S. Then:
Expevii-2 2IV(H(n,, w)) min (Un +
SS
(T) (V,H((n, w))l
De (0, 1),1 E (0, cvn - 2)}
(24)
2 e ( 5'
(25)
(26)
The first relation follows from Lemma 3 and the second follows from Lemma Lemma applies
since Ex+2 (S') S S. so VV (S") < |S|
< 2"
But then (x ze j S contradiction, so we obtain our desired statement.
[8]. which implies that Expevat2(S)) & S. This is
A.1.3 PROVING THEOREM
All that remains to massage Theorem into the form of Theorem I Let S (m.g. be any interesting class.
Lemma 5. C is not 2e 26" -robust to L p--perturbations size cv/gh +
Proof. This is a straightforward corollary of Theorem since construct a hamming graph out of (.,) as shown in Figure in the main text.
In detail: let M (HH(nggh, 2*) - (b) be the following bijection: first let Q be a set of 2n equally spaced values between and I, where the largest value is and the smallest is 1. Then the elements of ((H(n) qh, 2*)) can be viewed as Q=²th, We then map elements from Q=² gh to In,g,h,(b) such that the inverse operation is flattening of the image tensor. Note that such mapping preserves graph distance ((H(n2gh (h, 29)) Hamming distance on In.g.h.(b)-
14

---

Published as a conference paper at ICLR 2023
Let C' C be the set of images that are robust L pe-retuurbations of size c/qh + Let S M (C) and S' = (C' S' is then the set vertices for which no path with cv //gh**++ +n edges or less leads to vertex outside of S.
C' is an interesting class and M(.) preserves cardinality due to it being a bijection. Therefore
|C'| & [V(H(n /22 so by Theorem 4 we have |S///S|| < 2e 2e-2<² Again, since M(.) 2e-2c" preserves cardinality, this implies that |C"I/IC| 2e 20² which means that C is not 2e 2c -robust to L perturrbations of size c/gh nt + 2.
We remark that if the domain of MM() changed H(qn?, ,12),, the above argument also shows that C not 2e -2= -robust to cv/r + 2 pixel changes.
It is straightforward to generalize this to p-norms with larger p-
Lemma 6. C is not 2e -2c -robust to L -P-perturbattons of size (e//gh + 2)
Proof. Let S1 be the set of images that are r-robust to L -eeeeuuurasss size d, and let S₂ be the set of images that are r-robust to L -e-tpuruuraaioons of size d=/pp
Suppose I S1. Then there exists some image I' in different class from I such that ||z l' s d. Therefore, for all p > O, we have:
d 2 || l'l
(27)
Σ [1 glll
(28)
s,8.c
Σ Loyie I'a
(29)
2.9.c
= - I'Ip))
(30)
Where the second and third relation follows from the fact that channel values are contained in [0, 1]. Therefore, I & S2 either since || 17-7' 1'ppp - d3/p. Taking the contraposition yields S2 S St.
Setting d = c n and applying Lemma 5 gives the desired result.
A.2 PROOF OF THEOREM 2
A.2.1 ANTI-CONCENTRATTIO INEQUALITIES
We first prove anti-concentration lemma concerning the binomial distribution.
Lemma 7. Let X be random variable following the binomial distribution with trials and a probability of success of 0.5. Let Y be discrete random variable independent of whose distribution is symmetric about the origin. Then for any where t < E[X] and t [t| = 1/2, have:
PXX <1)
(31)
Proof. We have the following:
P <1) +
(32)
+Pr(X +Y
Pr(X < t) + +
(33)
+ +XXX+Y>>XX
15

---

Published as a conference paper at ICLR 2023
Therefore it suffices to show that Pr(X + any r 2 0:
< t). We have for
Pr(X + +
Pr(Y - - =t+
(34)
2 Pr(Y > r)Pr(( =t+r)
(35)
2 Pr(Y - Pr(X +Y > t =
=t-r)
(36)
(37)
Where Equation 34 follows from the independence of and Y, Equation 35 follows from the symmetry of the distribution of Y, and Equation 36 follows from assumption that / < [[X] and
t -- [t] 1/2.
Summing all positive for which Pr(X + r) 2 0 yields the desired result.
Lemma 8. Let X1, X2...., X, be independently and identically distributed random variables such
that each X, is uniformly distributed on 2k evenly spaced real numbers Pi < T2 < < 12k b.
Then for > we have:
2t 2 Vribb a)
Pr
X
<
-
- (b)))))>>
(38)
1=1
1=1
Proof. Let Y1, Y2.... Yn be independently and identically distributed Bernoulli random variables with p = 0.5. Let Z1, Zz,... Zn be a set of independently and identically distributed random variables uniformly distributed between the integers between and inclusive. If the Ys and Zs independent each other as well, we have:
b - (KY, + Z, EJK,, + Z))
X E(X,))
(39)
2h:
1=1
b
2, E
h:
YJ) + Σ
2k
k
1ml
iml
E((D)))
(40)
Z
Let n Yi = B, 1=1
D. and k b-a
c. Then for any 0, we have:
k
2k-1
16

---

Published as a conference paper at ICLR 2023
-t) -- - +
Pr( [X,
(41)
1=1
2rr(B+D
$ t + E[B] u)
(42)
PPr < + E 1)
(43)
2Pr - B[
2
1)
(44)
b a
Pr(B B[B]
2t
E
1, 1,0))
(45)
2
2
[n/2]]
2f
+ 2)
(46)
Where 2 u 2 is chosen such that +
the average of two adjacent integers. Equation is then an application of Lemma since B is binomially distributed with p 0.5 and D has distribution that is symmetric about the origin, and Equation 46) follows from the fact that no more than x + values are supported greater than (n/2)) )-m
c
43
interval of length and no supported value has probability
Observing that 12 (2m/2))2~ desired result.
due to Lemma 1 and substituting with -- (b- a) yields the Vn
A.2.2 PROVING THEOREM 2
Let A In.g.h.00 + f0, 1} be described by Algorithm [ an image, sums of its channels, and outputs if the sum less than n² 2 and otherwise. Let Z be the class of images that A outputs 0 on. Note that Z is an interesting class since it cannot be larger than its complement, so it suffices to prove that robust.
In other words, is the classifier that inputs
Lemma 9. Z is (1 Ac)-robust to L peerturrbations of size ev e
Proof. Let Z' S Z be the set of images in Z that are robust to L -erturbattions of size cygh n 2. Let be random image sampled uniformly. Then |Z'| Pr(T E 22 We then have the following:
Pr(I E Z') Pr( Σ Layaa +c // n
n² n22h/2)
(47)
2.y.a
Pr(
Lana S n2qhh22 c/ qh x 1
(48)
2.1.0
2c
(49)
2
Where the last inequality follows from Lemma 8 since each channel is sampled from a uniform
distribution over set of 2d evenly spaced values between 0 and 1. Noting that / < 2(""gh2*)-1 since it cannot be larger than its complement yields Iz'l - > 1 - 4c. Therefore, Z is (1 -co-ustust to
L' -ereutturbations of size evqh n 2.
Lemma 10. Z is (1 4c)-robust to de-perturbations of size e
17

---

Published as a conference paper at ICLR 2023
Proof. It suffices to show that image that is robust L' L' "perturbations of size d also robust to L pertturrbations of size d, since the statement then follows directly from Lemma
Let I be an image that is not robust to L" perturraaiins of size d, there exists some I' in different
class such that / o I d. Then:
d | 1loo
(50)
Σ
T.a.y.all
(51)
(x.y.a)
2
Tamaa
(52)
(0.3a)
I'll
(53)
Where the second and third relations hold since channel values lie in [0. 1].
This implies that is not robust to -eppttturbttions of size d. Therefore any image that is not robust pertperuurattions of size d is also not robust L --pertturbations of size d. The contraposition yields the desired statement.
(ey/Thinn 2/ 11- 177 for 2 2.
Lemma 11. Z is (1 rco-robust to TP IP-perturbations of size
Proof. It suffices to show that any image that is robust to L perrturraations of size also robust to L uP-perturbations of size (21-1j0-777 for any p 2 2, since the statement then follows directly from Lemma 9
8//y
Let I (b) be an image that is robust to L peerturbations of size d. Let I' be any image in different class, so | - ll > d. Then for any 2 1:
|| 1
Σ (an
Mm - L' Izy..aa''
(54)
(8))-)([2.11 1 L. y
Σ
(55)
(20 -1)
(x,81a)
1 (2b (2b-1)
(2 1),,,, Ioy.
(56)
(2))1a)
(2 1) || - I'll1
(57)
(2b 1)P
(58)
(2b 1)p-1
Where the second relation follows from the fact that if two channel values differ, they must differ by at least T
Therefore, || 1'1p
(2 176-17p for any I' whose class is different from I, so I is robust to
d/r
I. JP-perturbbations of size
4/r
for p 2 2.
(2 1175 1775
A.3 PROOF OF THBOREM
We fix arbitrary g. h, and b. For simplicity, we define N = n2gh as the data dimension. Let
C' C (I. be any interesting class. Our objective to show that is not robust to various perturbations.
For the first part of the proof, we construct grid over the unit hypercube and then map (n)), to cells in this lattice while preserving distances up to constant factor.
Let be a set of 2 disjoint intervals of equal length whose union is the interval {0. 1] (specifically, have T ([x 2-b (ar + 1) 2-
)) pr Zn (0,2 2]} U [11 2-b 1]))
18

---

Published as a conference paper at ICLR 2023
Let T be their Nth Cartesian power. This forms partition over the unit hypereube [0, 1]Mv since the elements of T are disjoint and their union is precisely the hypercube. Note that each element in the partition has equal measure.
We can associate each element of (..)) with an element of TN We first map (..). to [o, 1]", which can done by flattening the image tensor (which we denote by (II) for image / E (n). We then map that point the element of T the point falls within. The overall mapping is bijective, and we will denote it by F.
This completes the construction. To recap: each element in (n.g.h.(b) is now associated to cell in TN via F (.)) + T TN is partitioning of the unit hypercube into cells of equal measure. In the next part of the proof we define an algorithm that is able to find small perturbations. We then show that this algorithm succeeds with high probability, which proves the statement.
Let A [0, 1] x R + 10. U {L} be partial function that maps a point p1 and a real value to a point P2 such that the following hold:
1. 1p1 -Pell2 c.
2. Let 1 12 E Inggh1))) such that p E F(1)) and pa E F(2).. Then we require that
11 E C = 12CC.
A(.) returns 1 and only if no such P2 exists.
We can then define procedure FINDPERTURBATION for finding perturbation given an image I, which is outlined Algorithm
Algorithm 2: Find Perturbation
Input: An image 7 E C and real value
Result: An image 1' E (o,) such that & C, or I.
Sample P1 from F(I) uniformly at random;
P2
A(pI.c)
P2 = =1 then
return 1;
else
Find I2 & such that P2 F(22;;
return 72;
Our proof strategy is show that the perturbations found by FINDPERTURBATION guaranteed to be small, and that the probability of failure is low. This must then imply that most images are not robust.
Lemma 12. I' FINDPERTURBATION(L.. is nor 1, then |I I' <c 2
Proof. Each element of N has diameter of VNN 2h thus differs from (() by at most that distance.
Similarly, differs from (12) = b(1') ) by that distance. We also must have || P2 l2 S since
f I. Putting it altogether with the triangle inequality we get [Jb(T) >(I') 1|2 W c + 2 N Since b(.) preserves distances, we get the desired statement.
Lemma 13. If is drawn uniformly from C, then P 1) 2e -2
Proof. Let FCC) denote the image of C under F. Let F(C) denote the union of all elements in F(C).
If the input I is drawn uniformly from C, then P1 is distributed uniformly UF(C). The procedure fails if and only if A(pi,c) = I, which happens and only if all elements within a radius of from pl all belong to F(C). Let C' denote the set of all such points.
19

---

Published as a conference paper at ICLR 2023
p(()) Pr(A(12,c) = p(UF(C))
(59)
< 2e 101
(60)
Where u(.) denotes the Lebesgue measure.
The last inequality comes from Theorem 5 which is given in the next section. The statement applies for any set S formed from a union of elements of T whose measure is no larger than 1/2. ((C) satisfies these criteria since C is an interesting class and each element of T of equal measure and disjoint, so we attain the desired statement.
Lemma 14. C' is not 2e 2e- robust to 1.2 -e-petuurbations size c. + 2 2
Proof. Let be drawn uniformly from C. Let C, be the set images that are robust to L perturbations of size + 2 V 2m
Let l' = FINDPERTURBATION(L, c). Then I' is randomly distributed over (o,) U(L}. By
Lemma 12 E In.g then || - l'll2 & - 2 2 which implies that I & C... By
contraposition, E C, implies that FINDPERTURBATION(/ = Therefore:
Pr(T' = 1) Pr(I C,) Pr(I Cr, 1)
(61)
Pr([ E C,)
(62)
|r
(63)
ICT
By Lemma 13 Pr(I' = =] 22-2/2 Thus,
|C TC
22-21 which yields the desired statement.
Lemma 15. C is not 2e 2 -2 to IP -P-perturbations size (c+22 2
VN 2/p 26 for 2 2.
Proof. We use the identical argument from Lemma 6
Let Sj the set of images that are r-robust I.2 -e-petuurbations of size d, and let Sg be the set of images that are r-robust L L'-perturbations of size dRíp, where p 2
Suppose I E Si. Then there exists some image I' a different class from / such that || - 1' s d. Therefore, for all p 2 2, we have:
d > I 1-1
(64)
T Iz.g.el? 1
(65)
(66)
(| - 1'lpp)"'
(67)
Where the third relation follows from the fact that channel values are contained in [o, 1]. Therefore, & Sy either since ||z - 1l < d//r, Taking the contraposition yields S2 S St.
Setting d N and applying Lemma 14 gives the desired result.
Substituting VN- Vqli Lemma yields the exact form of Theorem
20

---

Published as a conference paper at ICLR 2023
A.4 PROOF OF THEOREM!
5
Our objective in this section is to complete the proof of Theorem 3 by proving Theorem 5 stated below. We will use sr(.) to denote Lebesgue measure throughout this section.
Definition 4. We say set S S [0, 1|"h is regular set if there exists some finite set T such that S - i and T consists of elements that ure Cartesian products of n intervals that are either open or closed.
By this definition the sets defined in the proof of Lemma 13 are regular, so the following theorem is applicable.
Theorem 5. Let S S [0, 1]" be regular set such that p(S) S 1/2. Let Sp S S contain all the points in S such that for all [0, 1], | vll2 S y S. Then S(S)) 12 H(S)
A.4.1 PROPERTIES OF THE STANDARD NORMAL DISTRIBUTION
First, we define the cumulative distribution function for the standard normal distribution and its derivative.
((x) -
1122
(68)
2tT
-00
('(x) 1
(69)
22T
Similarly to the discrete case, the ratio of the cumulative distribution functions monotonic increas- ing.
Lemma 16. ((r-k)
is monotonic increasing for all k 2 O.
(w))
///2 T- --1t/90
Proof. Let f(x)
Then:
-e- 12 1 e c - 22-122 (S (2d))
d dx
[(x)
(70)
When x 2 0, this derivative is negative since both terms in the numerator are negative. If x < 0, we have the following:
20
6
-1
x
c
8-/2
+
e 12 12
/2
(71)
-00
00
- -2/2
(72)
(73)
So the sum is strictly smaller than (e- (2-2 -e-=2=2-===213 12-2
Therefore, the derivative is everywhere
negative, so f(x) is strictly decreasing.
Therefore, we have the following for any non-negative
d 4(x -(x-k)) = f(x -k -k- [(x) 2
In
(74)
dx
((x)
Since (n(.) is monotonic increasing function,
(xx-k) must also be monotonic increasing. (x)
21

---

Published as a conference paper at ICLR 2023
A.4.2 PROVING THEOREM 5
Similarly to the discrete case, our main result relies on an isoperimetry statement, this time on the unit hypercube (Barthe & Maurey| 2000).
Lemma 17 (Isoperimetric Theorem on the Unit Hypercube). For any n, let A C [0, 1I be Borel
set. Let A, {ir E [0, [||]"r E A || x'1l S c). Then we have the following:
inf (A(e) (((A) +
2TT ( (u(A)))
(75)
Let C' [0, 1] be regular set such that (CC) S 1/2. Let Cr C denote the points P1 in C such that for any point P2 E [0, 1), [pp: - p2ll2 T = P2 E C.
Lemma 18. C. - ( (c(C)) - r)
Proof. Let Φ (m(C)) and let (xx +(x =). Let u(.) be Lebesgue integrable function such that the following holds:
(-s0.) v(t)dt [m(C_r) if 0 (u(Co) otherwise
V(r)
(76)
This exists since C' is a regular set. Since Viz) results from integration, it is also a continuous function.
It then suffices to show that Vxx) s f(x) for all x, since (x) corresponds to the left hand side of the theorem statement and (x) corresponds to the right hand side. Suppose this not the case. We know that ((x) S (ar for all x 2 O, so if this is violated it must happen when x < 0. Since V(x) and fxx) are both continuous, by the intermediate value theorem there must exist some interval [a, 6) where V (x) > f(x) if E [a, b). (b) = fbb, and < 0.
This gives us the following:
f v(t)dt (o.b)
V(b) V(a)=
(77)
V(t c(t+c)-((t) dt
lim (a,b))
(78)
++0+
u(C_1-e) p dt
lim c-10
(79)
(a.b)/
V2T (((0~((((C,))))
(80)
(a.b)
V2T /2
(81)
(a.b)
f(b) f(a)
(82)
Where the set values where the limit Equation 78 is not equal to v((), which by the Lebesgue differentiation theorem is a set of measure 0. Equation 80 is application of Lemma [7] which is applicable since C-,, is Borel set because f(x) < V(x) for all E (a, b) and the fact that (0(0-1()) is monotonically increasing if the input no greater than 1/2.
a regular set. Equation 8T follows from the fact that
We also have V(a)= f(a) and V(b) f(b), it must be the case that V(b) - -V(a) f(b) f(a). This contradicts the above, so it must be the case that V(x) < fxx for all x.
Lemma 19. ((C.) -0 (2)(())
22

---

Published as a conference paper at ICLR 2023
Proof. Let (u(()) Then for any 2 0,
clC))
4(2 cc) 41122 -c) c) ((1/2)
2e- -
(83)
((()
(2)
Where the first inequality follows from Lemma 18 the second inequality follows from Lemma 16 and the fact that j(() 2 1/2, and the third inequality follows from the Gaussian tail bound
(x)
/2 for all $ 1/2.
A.5 AVERAGE DISTANCE BETWEEN IMAGES
We wish to show that for pair of images 1, E (n.ghh((b) that are sampled independently and uniformly, there exists a k such that:
B|ll [lll 2 Nb. max(1.p)
(84)
If p = 0 then set kp to 2 and the relation will hold with equality, so we are done. Otherwise, note that have:
E 1' I [aa N =EJX Y maxx(1.p)
(85)
Where and Y are independent random variables that are both drawn uniformly from a set of 2 equally spaced values, where the largest is I and the smallest is O. For simplicity, we denote E||x mmax(1,))) with 2.
|| 7' [' ma)) is non-negative and cannot be larger than N. Therefore, the probability that | I' I' (1x((1))) 2 N2/2 is at least 2-
Via a monotonicity argument we can deduce that the probability that || Fllp > (z/2)1/ max(p.1) / 1/ max(p.1) is at least - well. We can then apply Markov's incquality to get the following:
Bill 1'11 2
2 (z/2)²/ max(p.1) N2/ max(pp1)
(86)
By setting k to be 2 (2/22/) max(p.1) we attain our desired result.
A.5.1 AVERAGE DISTANCES BETWEEN IMAGES FROM NATURAL DISTRIBUTIONS ARE ALSO LARGE
The above analysis shows that average distances between images over the entire image space is large, but it does not preclude the possibility that average distances between images from distribution of natural images is small.
To investigate this, we computed average distances between images Imagenette, subset of Imagenet consisting of 10 classes (tench, English springer, cassette player, chain saw, church, French horn, garbage truck, gas pump, golf ball, parachute)(Howarde
In detail, we took all the images within the training set of Imagenette with the shorter side resized to 320 pixels and discarded all images that were not in RGB, resulting in 9296 images. Each image had bit depth of 8. We then cropped the images such that only the top left 320x320 pixels remained. We then computed the average distance measured in p-norms where p ranged from to 5:
EXED E EyED ||
vllp
(87)
D
23

---

Published as a conference paper at ICLR 2023
320x320
160x160
80x80
40x40
20x20
Figure 3: Subsampling 320x320 images to smaller sizes
Where D is the set of 320x320 images. We also subsampled the images to 160x 160, 80x80, 40x40, and 20x20 by taking the top left pixel of each region as the representative sample (see Figure (3) and computed the average distances between them too. The results are presented in Figure and indicate that the average distances between images drawn from natural distributions are not dramatically lower than those between images drawn uniformly we believe the Imagenette dataset sufficiently representative of natural image distributions.
The average distances between uniformly drawn images were each approximated with 200000 pairs of randomly drawn images, except for the 1-norm where a closed form solution exists: for pair of nxn images with channels and bit depth b, the average distance between all pairs of images, measured with the n-norm, is h,?h, where o is given by:
D Σ
26
(88)
22b
A.6 PLOTS OF THE RELATION BETWEEN ROBUSTNESS AND PERTURBATION SIZE
We plotted the curves defined by the upper bounds in Table to facilitate interpretation. The curves are plotted in F5 h, b, and have been fixed at 3, 8, and respectively, so the bounds apply to square RGB images where each channel has a bit depth of 8. Perturbations sizes are then plotted on the y-axis, and corresponding upper bound on the robustness achievable is plotted on the æ-axis on a logarithmic scale. Sizes are measured in O-norms, 1 --nomms, and 2-norms, and we plot these curves for n = 32, 256, and n 1024.
24

---

Published as a conference paper at ICLR 2023
100000
Natural images
Natural images
200
80000
images
images
(1-norm)
Average 2.noml
150
100
40000
20000
50
20x20
40x40
Image
Image size
Natural images
Natural images
Average distance
images
Average distance
10.0
images
[3 (-nom)
(4 (anorm)
255
Image size
Image size
Natural images
6-
Aver age distance (S-narm)
images
Image size
Figure 4: Comparison of average distances between images from natural distributions with average distances between uniformly drawn images various p-norms
25

---

Published as a conference paper at ICLR 2023
32x32
32x32
100
4.0
Perturbation size
(0-norm, 1-narm)
3.5
80
Perturbation
(2-norm)
30
25
40
15
0.001
10
0.1
Upper bound on robustness
Upper bound on robustness
256x256
256x256
7.0
Perturbation size
(0-norm, 1-form)
600
Perturbation
(2.oom)
6.0
500
5.5
5.0
0.01
0.001
1.0
0.1
0.01
000
Upper bound on robustness
Upper bound on robustness
1024x1024
1024x1024
3500
17.5
(0-norm, 1-morm)
3000
Perturbation
2500
Perturbation
2-norm)
16.5
2000
16.0
1500
15.0
10
0.1
0.01
0.001
10
0.1
0.01
0.001
Upper bound on robustness
Upper bound on robustness
Figure 5: Relation between perturbation sizes and corresponding upper bounds on achievable robustness of interesting classes.
26

---

Published as a conference paper at ICLR 2023
B APPENDIX
B.1 ADAPTING OF LEMMA FROM (HARPER) 1999)
In this section we will show how we adapt Theorem 3 from (Harper 1999 in its exact form into the form given Lemma
B.1.1 PRELIMINARIES
1999 its original form. We note that the terminology concern elements from the unit hypercube [0, 1l"
Some additional terminology is required parse Theorem 3 from (Harper
H (z. y) used denote the Hamming distance between elements x, E [o, 1]d, in other words the number of coordinates at which they differ.
lower set is set 5 S [0, 1]d such that if E S, then any vector y [0, 1] with the property S 24 for all where 1 - i S d is also in S.
weighting is vector in (0, 1)d that splits the unit hypercube [0, 1] into 2 distinct regions. The [10,4]
set of regions is x x 4,), (4,, 1]}. and it is said that is constant if L = lj for all i, where
1 S i
and J S Here we use x to denote the Cartesian product.
H Br, d) with weighting is subset of [0, 1] and is referred to as Hamming ball of radius r. A Hamming ball of radius r is usually used to denote a subset of {0, 1]d that contains all vectors where the sum of the entries does not exceed This concept can be naturally be extended to [0, 1] with weighting t: if we define F, as a map that maps 0 to [0, t.] and 1 to (f,, 1), we have:
BB(r, U P((ss
(89)
eEH.
Where H, Hamming ball of radius in the traditional sense.
B.1.2 ADAPTING THE NOTATION
We are now ready give Theorem 3 as it is stated in (Harper 1999).
Theorem. Yu, 0 < < 1, 3r such that H B(,,, minimizes
| (r. d)l = Hy $ S Ex E H,, < hyl
over all lower sets, S S [0, 1]4, with |S| = v. The optimal weighting for HB(r, d) constant
To bring the theorem statement closer
terminology, we have Exp* (S) (y Er S, (x, 3) h). Since the volume of S is constant, H Br, d) also minimizes Exp* over all lower sets S of given volume. Note that for our expansion notation to make sense here, we act as though [0, 1jd is an infinite graph where there exists an edge between any pair of vectors that differ at exactly one index.
Since the theorem states that the weighting t should be constant, we have an exact form for HB(r, d). Let p denote the value of all entires of t. We then have Hl B( d) = Udp(r) and (H d))l Ur h).
Therefore, for any lower set must be the case that
Exxx(S)) 2 min |xpx min( (HB(r, d))
[S]}
(90)
min hh r 00, d h), E (7) [
(91)
We then restate Theorem from HHarper 1999 in the following form:
27

---

Published as a conference paper at ICLR 2023
Lemma 20. Ler S & [0, 1]"h be lower set. Then:
Exp* (S) 2 min(Un,pr (r+
(r) = -|| E (0, 1), r [0, k)}
Note that we have replaced d with n and h with & to match our notation. This is now nearly in the form of Lemma []] All that remains to show that this inequality implies an analogous one for Hamming graphs.
B.1.3 EMBEDDING HAMMING GRAPH
Let [w]] be the set integers from to w inclusive and let H(n, w) be the Hamming graph with the vertex set [w]". If [w]", we call it lower set if x E S implies that any y with the property that S. xy for all where 1 S i S is also in S.
Lemma 21. For all C [w]", there exists lower set S' where |S = [S] and |EEp*' (S") S [S))
Proof. Let S S [w]". Let i be an index such that there exists some S and y & S such that Y: < 24 and for all j yÜ S Tj. If not such exists, then we are done, since S must be a lower set.
Group together all vertices that are equal on all coordinates except i. Each group contains exactly elements. For each group G, reorganize which elements belong to S by moving them to the bottom. Denote the new set by S*. For example, suppose that G n S {(1, 2, 2), (1, 3), (1,2,5)), and i = 3. Then we will shuffle those elements downwards such that we get G n S {(1, 2, 21, (1, 21).
Note that this action cannot increase the size of the expansion. Given a group G, consider the number of elements that are not in EXP*(S). Denote by z. If = = 0, then that number clearly cannot decrease after reorganization.
If z e O, then no vertex that is within & steps of any element of G' is a member of a group G' such that GG' nS > z. Otherwise, G must have more than w z elements that can be reached by those elements
steps, which means G must have less than 2 elements that are not in ExP"(S).
But then that means Exp* (S*) cannot reach more than w 2 elements of G. specifically the ones where the ith coordinate is at most w - 2. Therefore, G has at least 2 elements that are not in Ex*)(S*). Therefore (Ex*"(S G)l S |ExP*(S n G)), and since every vertex covered by exactly one group, we have |Ex** I |EXP*(S))
We can keep iterating this. With each iteration, the sum of all coordinates of all elements in S will strictly decrease, and since this sum positive, this process will eventually terminate, leaving us with a lower set S' that has equal size and with an expansion that is no larger than that of the original set.
We map elements from H(n, w) to subsets of [0, 11"h via the following map:
F((1) xx,)) = I1 Æ1
22
22
En
1
In
x
x
(92)
w
w
This mapping preserves expansion for any set S in the following sense:
U
F(x) = EXPx F(x))
(93)
=EE
#ES
Furthermore, we have for any set S:
|
= U F(*)
(94)
(H((n,)))
#ES
28

---

Published as a conference paper at ICLR 2023
Finally, this mapping also preserves the property of being a lower set.
Therefore, for any set S S H(,, w), we have:
ExPx V(H(n, w))l
EXP*(S) SS' C H(n, w) is a lower set, |S = [S]}
2 min( [VHH(, w))l
(95)
=minfl
U
F(x) 18' C H(n, w) is lower set, |S = |S|]}
(96)
(EE
H(n, w) is a lower set, |S |S]} min Exp* U F(x))
(97)
xES
|S|
min (Xx=(()) | [0,1]] lower set, |S'
(98)
[V, w))l
|||
min(Un,(r + k) (r) VV [VH(n, w)]l P (0, [0, K)) (99)
The second and third relations are properties of the mapping F, the fourth relation holds because we are expanding the set of sets that we consider, and the last relation follows from our derivation in the previous section.
The gives the statement of Lemma 3
which we restate here for convenience:
Lemma (Isoperimetric Theorem Hamming graphs). Let S & H(n, w). Then:
Exp* (S)
2 min min(Unp(r++ +
VVH(nn w))l
S
(n)(() (V(H(n, w))l Pe (0, 1), E [0, n k))
29


Reviews:
[{"review_id": "rbcGRrrv0tw", "reviewer": "Reviewer_sETu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves an isoperimetric theorem for the image space. Specifically, it shows, in the pixel space of images, for every class of size less than half of the space, most of the points in the class are located on the boundary of the class (hence a small adversarial perturbation will move the point out of the class). \n\nThis claim is not surprising in high dimensional space (in fact, it is pretty intuitive). Their proof is also based on the existing result on Hamming graphs. However, I think this is a very interesting paper, because in retrospect, I am surprising that people previously did not realize this simple fact. In my opinion, this is like the “no free lunch” theorem in the Generalization theory, which gives a very simple but important lower bound of what can be learned and what cannot. \n\n(The paper also has a few additional results, including the bounds they have are tight by giving one specific synthetic example, and also improvement of the bound when adjusting the bit depth of the image space)\n\nTherefore, I think this paper is a clear accept. \n", "summary_of_the_review": "This paper provides a very simple but important lower bound argument of the robustness in image space, based on the isoperimetric theorem in Hamming graphs. The result is very good to know, for people doing research in robustness ML. ", "strength_and_weaknesses": "For a long time, many people talk about the origin of adversarial examples. Some people believe this is due to the inherent structural problems in neural networks -- this might be true, but this paper provides a completely different perspective. This paper proves that, no matter which algorithm we are using, we will always get adversarial examples. The adversarial examples are the products of the high dimensional image space. \n\nThis gives a very nice lower bound of robustness theory, just like the no free lunch theorem for Generalization. Similarly, I think this is not to say that we will not get anything robust for real problems, that is too pessimistic -- just like no free lunch theorem does not imply that we will not get anything learnable. Instead, it tells us that we should be more careful about the notion \"robustness\", e.g., with additional priors or assumptions, otherwise nothing is robust. \n\nI think the paper can be further improved with the following two aspects: \n\n1. Can the authors describe the relationship/gap between their main theorem and the actual real data distribution? At least from my own perspective, for datasets like CIFAR-10/Imagenet, if there are M classes of images, the total mass of all the classes is less than half of the space. The most points, belonging to the uninteresting class according to Definition 1 in the paper, can be seen as some noisy/weird points. In that case, it seems that the main theorem is still true, but after perturbation, the perturbed points will move from certain interesting class to an uninteresting class. In practice, what we observe is different: these points will move to other interesting classes. To me, it seems that designing a good model that can incorporate the notion of uninteresting class does not violate the main theorem, but is very useful in practice. Can the authors comment on this? \n\n2. Can the techniques for bit-depth also applied to the size of the image and channels? It seems to me that all the four dimensions are symmetric, so why is bit-depth so special here? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kU0PbJhvNPm", "reviewer": "Reviewer_K2cJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work seeks to understand the limits of robustness of any image classifier. The framework here considers images as discrete objects on the grid space of (spatial dims n  x channels h ) with each entry in [0,1] representable by a finite bit string of \"depth\" b.  \nLet I_all denotes all possible images that can be represented as described. Each classifier induces a partition of I_all based on predicted labels. \n\nThe authors make the following novel observations that are independent of the image distribution and any properties of the specific classifier (beyond the induced input partition) -\n1) Most images in any class partition can be shifted to an image in a different class partition by a perturbation that is O(n^{1/max{p,1}). Or w.p. at least (1-delta), any uniformly sampled image in this class is vulnerable to perturbations of size O((\\sqrt{n^2 h log(2/delta) })^{1/p} ) for p in [1,\\infty). \nThe required energy of perturbations vanish in comparison to the expected distance between any two uniformly sampled image from I_all. \n\n2) The above statements are asymptotically optimal as image size n -> infinity. Thus better rates require further assumption on the data distribution or the classifier properties. \n\n", "summary_of_the_review": "This work shows a fundamental limit of robustness for image classifiers, albeit in a worst-case setting where all possible discrete images of a certain size are considered. The main result is asymptotically optimal and leverages novel techniques using expansion properties of Hamming Graphs. While rate optimal within the framework considered, the results demonstrate that understanding robustness requires further accounting for properties of data distribution or indications of such via the trained classifier. \n ", "strength_and_weaknesses": "# Strengths : \n1) The analysis appears to be technically sound and best one could seek to establish under this setup.\n2) The incorporation of discrete image space via expansion properties of hamming graphs was insightful and could spurn other results. \n\n# Weakness : \nThe authors favorably view their work in comparison to cited work Fawzi et.al. 2018. I agree that the result here is better for its extension to any entry-wise p-norm and restriction to discrete image spaces. However I contend that the distribution-agnostic flavor of the result is a weakness rather than a strength. For eg. \n1) there is an implicit assumption that the union of pre-images of class labels C^{-1}(y) should cover the entire discrete image space. \n2) Real data distributions are certainly not supported on any possible image in I_{all} and requiring a uniform level of robustness at any such image is a pessimistic objective to begin with. \n\nThere are implications from these points that weaken the final inference of the stated results. \n\n- The statement \"w.h.p of uniformly an image from C^{-1}(y)\" now includes images that humans would ostensibly consider random noise but that which a classifier might faultily predict label \"y\". In fact every random noise or approximately random noise image is present in the set I_all. The authors indeed indicate this - \n\n_\"Our bounds do not immediately preclude the existence of small fractions of images within interesting image classes that are robust to large perturbations, and it is possible that those are precisely the set of images that are commonly encountered in deployment. Therefore, our bounds do not directly prevent the construction of classifiers that are robust with respect to some given image distribution\"_\n\n- Ideally the notion of *interesting classes* should capture the data-distribution as subsets of C^{-1}(y) that exclude regions of input that have measure zero. The current characterization of interesting classes is weak in this regard. \n\n- The expected distance between images from real data could be far smaller than the expected distance between any two uniformly sampled images in I_{all}. This could render the adversarial energy at which a point is non-robust much larger relatively. For example the denominator in LHS of equation (2) might be much smaller and hence the upper bound might not vanish or vanish more slowly. \n\n- Further the quality of such a result in a non-asymptotic setting is more relevant as real image data typically have n <= 224 (outside of medical imaging). When n -> infinity, I might expect a standard concentration phenomena that places more weight on exterior /edge of I_{all} which further worsens the lack of distributional information. My intuition is that the gap between expected distance between randomly sampled data under a specific data distribution P vs expected distance between uniformly sampled images grows with n making the analysis potentially looser asymptotically in the context of real data. (Note : This last thread of logic is unverified informal intuition and I would be happy to see arguments for why it is not the case). \n\n- To summarize, here's a statement from the paper - \n\n_\"Then for most images, a tiny perturbation can make the given image trigger undesired behaviour, ostensibly making the classifier unreliable.\"_\n\nIt is my opinion I think the result does not make a statement for *most* images of a real data distribution and the adversarial energy might not be *tiny* in comparison to expected distance between images of different classes. \n\nAs a *concrete actionable feedback* I suggest the following experiment - evaluate the expected distances between randomly sampled train/test data from a benchmark data set (say CIFAR10) and compare it with the theoretical limit under uniform sampling from I_{all}. \nFurther one could observe this distance as images are scaled to larger spatial dimensions (which act as proxy for a true image distribution with larger n). These experiments could bolster the effectiveness of the main result. \n\n\n- As a final observation, Section 3.3 aims to demonstrate that brittle features (such as line-drawings) can impart non-trivial semantically salient information. I agree with this observation but would like to point out an asymmetry : real data aren't well approximated as random noise + line-drawings. Image (c) in Figure 2 shows that removing (a) can fundamentally change the semantic content but Image (e) shows that this isn't necessarily the case for real images. So, removal of brittle features might not remove all semantically salient information even if addition can impart them. I contend that an ideal characterization of meaningful images should exclude Image (c) as the signal-to-noise ratio is low. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fB2OmVrnhxp", "reviewer": "Reviewer_mJYy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies fundamental limits on robust classification in quantized domain $\\mathcal{D \\subset [0,1]^n}$. To this end, it is shown that whenever a classifier $f$ classifies less than half of all the points as class $c$, then almost no input $x$ such that $f(x) = c$ is robust in the sense that there exists an adversarial example $x'$ such that $||x-x'||_p \\leq O(\\sqrt{n})$ and $f(x') \\neq c$. It is also often shown that $O(\\sqrt{n})$ is asymptotically optimal. These results are presented for $p \\in \\set{0, 1, \\geq 2}$. ", "summary_of_the_review": "The paper shows that $O(n^{1/{2p}})$ is the maximal perturbation budget for which a reasonably robust classifier may exist for inputs from a subset of $[0,1]^n$. The techniques used are new in this field and overall I think this is an interesting problem with reasonably complete solution - there is still one case that is not fully answered - upper-bound for $p \\geq 2$.\n\n\n\nIf the errors in derivations are fixed and the statements are corrected (see misc of previous section), I will raise my score. I will also additionally raise the score if my other concerns are addressed/discussed satisfactorily (see ungood points and their details in the previous section - specially the related work part).\n\n", "strength_and_weaknesses": "The paper considers image space to be quantized. Then they form a graph from it, in a way that every possible image is a vertex and two vertices are connected iff they differ at a precisely one position. Such graph is called a Hamming graph and the distance of two vertices correspond to $L_0$  \"distance\" of the corresponding images. Thus, the original problem of - how big the adversarial budget have to be in order to make the majority point not robust - becomes similar to a so-called isoperimetric problem on Hamming graphs, and finally the result is obtained for adversary with $L_0$ budget. Since the considered domain is bounded, one can simply compute the minimal radius of $L_p$ ball containing the $L_0$ \"ball\" of given radius.  (thm 1)\n\nLater, a construction of a classifier is given for which the $L_1$ adversary can find just a few points that are not robust given certain budget, where the property is proved using anti-concentration inequality. Finally, the result is extended to other $p$-norms by calculating the budget of $L_p$ adversary that is contained in the given $L_1$ budget. (thm 2)\n\nFinally, the role of quantization levels is investigated yielding an alternative upper bound for the robustness when $p \\geq 2$.  (thm 3)\n\n### good points\n* The considered problem is quite natural and interesting.\n* The techniques used here seem to be novel in the field.\n* The paper provides both lower-bounds and upper-bounds for possible robustness and they are quite matching. \n* Clear exposition of proofs.\n\n### ungood points \nI believe they all can be fixed and later I provide more details on them.\n* The literature is not fairly credited.\n* Unnecessarily complex notation. An image could be a $d$-dimensional vector, now it is tensor of order $4$.Thus there are used unnecessary letters and they are sometimes overloaded ($n,q$ in the proofs have different meanings than they have in the main paper.\n* The result is disconnected from practice by considering by orders of magnitude larger perturbations than is commonly used.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "avrXf16Enc", "reviewer": "Reviewer_xoPQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present theoretical results on the robustness of image classifiers. Namely they demonstrate that for all image classifiers, the set of images robust to Lp-bounded adversarial perturbations becomes vanishingly small. The main technique used in the proofs is a novel approach leveraging Hamming graphs. The bounds provided are asymptotically optimal, up to constants. Some discussion human perception is also provided.", "summary_of_the_review": "Thiis paper provides novel theoretical results on the limits of robustness for a broad class of functions. The proofs provide matching(ish) lower and upper bounds, and are novel in their technique as well as investigation of bit-depth. However, the generality and nature of high-dimensional spaces do not lend themselves to providing results that seem to be applicable for many real-world cases where robustness is only considered as an epsilon-dilation of a lower dimensional manifold. Overall, I would like to see this paper accepted, however for the aforementioned reasons, I do not feel very strongly about it and am generally unwilling to work too hard convincing other reviewers in arguing for its acceptance. ", "strength_and_weaknesses": "Strengths:\nAdversarial robustness is an important and busy area of study. This work offers some insight into the impossibility of robustness of robustness for discrete-valued vector functions, using a novel proof technique. In particular, the consideration of finite bit-depth in the results in this work are interesting and novel. The theoretical results presented require very few assumptions and can generalize to all classes of functions. Further, it is quite appealing to see that upper bounds can be made tight(ish) by matching lower bounds. \n\nWeaknesses: \nMy only complaint with this line of work is that it may be interpreted as offering explanation for the inability for images from the data distribution (e.g. cifar10, imagenet) to be robust to Lp-bounded adversaries. While the theoretical results are sound, they do not necessarily speak to the applications of interest with respect to robustness. For example, consider all the images labeled 'cat' in the CIFAR10 dataset $X_{cat}$, and consider the preimage of the label 'cat' for some ideal classifier $\\cal{Y} = f^{-1}(\\text{cat})$. It is entirely possible that $\\cal{Y}$ is an interesting class, while simultaneously containing the union of $L_p$ balls for every $x\\in X_{cat}$: i.e. $\\bigcup_{x\\in X_{cat}} B(x, \\epsilon) \\subseteq \\cal{Y}$. While the results in Theorem 1 would still hold for the interesting class $\\cal{Y}$, one might also say that the network $f$ is robust to an Lp bounded adversary for the cat class. In this sense, while the proof techniques are novel and interesting, the results seem natural from isoperimetric arguments. Thus, it's unclear how applicable such results as these are to building the intuition of robustness researchers at large, given that it's generally believed that images live on a lower-dimensional manifold (and therefore have measure 0 in ambient space). Nevertheless, I think this complaint is relatively minor in light of the theoretical results provided, perhaps just a bit of overselling occurring by arguing this applies more broadly to adversarial robustness in-practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PONIdon0tHT", "reviewer": "Reviewer_vaeu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies fundamental limits on the Lp robustness of a classifier.\nThe main result is that under natural assumptions, any classifier on n x n images will be vulnerable to L2 perturbations of size O(sqrt(n)).\nThe paper further shows that the result depends on the chosen bit-depth of images.", "summary_of_the_review": "The main result of the paper seems technically sound, and the approach based on Hamming graphs seems novel and interesting.\nThe actual interpretation of the result is less clear to me.\n\nWhen comparing the robustness bounds to \"typical distances between random elements of the image space\" in Section 3.1., are these distances between images from the junk class? If so, this may not be the most interesting measure to compare against. The typical distance between elements of \"interesting\" classes would be the more appropriate point of comparison here.\n\nSections 3.2 and 3.3 try to give some interpretations of the result and implications for robust vision systems, but ultimately it seems that the right conclusion here is simply that drawn at the end of section 3.2: \"Another way of circumventing the barrier to constructing reliable computer vision systems imposed by our bounds is to note that a perturbation with a small p-norm is not necessarily imperceptible\"\nExamples such as the ones in figure 2 are not novel: similar argument were made in an early paper by Fawzi, Fawzi and Frossard which should definitely be considered in the related work: https://arxiv.org/abs/1502.02590\nIt has been known for a while that Lp norms are not good a metric for perceptual similarity. And so we know that small Lp perturbations can at times change classes, while large Lp perturbations might not (see e.g., https://arxiv.org/abs/2002.04599)\n\nIn light of this, it is not particularly clear how the paper's main result should be interpreted.\nUltimately, it is is simply a result about how input spaces can be partitioned to maximize distance between classes. Whether this result has any implications for robust classification is unclear.", "strength_and_weaknesses": "Strengths:\n- Interesting and tight result on the robustness of arbitrary classifiers\n- The paper is easy to read\n\nWeaknesses:\n- Not clear why the focus is on images, as the result seems to apply to arbitrary classification tasks\n- Unclear what the takeaway of the result should be. The paper seems to suggest that the result is some kind of fundamental limitation of robust classification, but Figure 2 simply seems to show that Lp norms are poor measures of semantic similarity (and thus poor measures of robustness as well). This is not a new insight. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster