Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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}$. 
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)

Later, 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)

Finally, the role of quantization levels is investigated yielding an alternative upper bound for the robustness when $p \geq 2$.  (thm 3)

### good points
* The considered problem is quite natural and interesting.
* The techniques used here seem to be novel in the field.
* The paper provides both lower-bounds and upper-bounds for possible robustness and they are quite matching. 
* Clear exposition of proofs.

### ungood points 
I believe they all can be fixed and later I provide more details on them.
* The literature is not fairly credited.
* 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.
* The result is disconnected from practice by considering by orders of magnitude larger perturbations than is commonly used.



clarity,_quality,_novelty_and_reproducibility: ### Clarity
* Overall the paper is well written. The exception is the usage of $n^2qh$ to denote the dimension instead of e.g., $d$ or $n$. The current notation is just annoying and I see no benefit of using it. I highly advice the authors to consider simplifying notation here. In a similar spirit, I think Algorithm 1 could be replaced with $f(x) = \text{sign}(\mathbf{1}^T x - d/2)$ for image $x$ for better readability. 

* Consider providing a "dual" table to Table 1, where we fix the perturbation budget and ask what fraction of an interesting class can be robust now. Specially it would be interesting to provide such results for images of CIFAR/ImageNet dimensionality and the standard radii. E.g., $\ell_\infty \sim 8/255$,  $\ell_2 \sim 1$ and $\ell_1 \sim 2$.


### Novelty 
* The proof technique adapted from previous works  seems to be novel in this field. The crucial tool of the paper is Theorem 3 of (Harper 1999). Unfortunately, the referenced paper states "We leave the verification of this as an exercise for the reader." The reader could not verify it by themselves. 


* While I think the paper is novel enough, the relevant literature is cited, but not sufficiently credited. E.g., this paper claims superiority over the previous approaches since the previous work produced results dependent on the data distribution, while here the result is independent of the image distribution. On the other hand, the previous approaches  derived results for uniform distribution, which is equivalent to the setting assumed here. Similarly, the result for hypercube is mentioned in the literature, but the provided literature review here suggests that considering discrete input is a new concept. The literature also already showed that the interesting things happen when the perturbation is of the size $\sqrt{d}$; thus, the results of this paper are somewhat unsurprising. That being said, I think the article addresses an interesting problem and as far as I can see, it doesn't follow directly from the literature. However, the literature could be credited more fairly. The results I was referring to can be found in the $3$ papers discussed in the last $2$ paragraph of sec 1.


### Quality
* There are minor problems listed below, but overall the results look correct (did not check thm 3 yet) and the problem solved is interesting. On the other hand, I do not see any direct applications of the results - this is somewhat expected for a theoretical work.

### misc
* Thm 1 the quantifier do not look right to me. The result holds when we consider any $c$, not just when we consider all of them.
* Thm 2 consider stating $1/4 < c < 0$.
* eq. (10), there should be $p^i(1-p)^{n-i}$, but there is $k$ instead of $i$.
* just before eq. (13). "by induction we have" - we don't really have it, it is the induction hypothesis.
* eq. (15), in denominator sould be $(1-p)^{n-x-1}$, later the same error in eq. 17 (also see typo in eq. 17, $U_n$)
* In lemma 4 we start with a given $r$ but later we define $r$ to be a median of the distribution and in the end we reference the original $r$ again. Please, make it unambiguous. Further, we needed to assume that $np+1-k  < E(X) = np $ so that we use Hoeffding's inequality; that is, $k  > 1$.
* Eq (21): there should be $\leq$ instead of $=$.
* Thm 4. There should be "path with at most X edges", not just "path with X edges".
* For eq. (25), my calculations yielded $(1/2)e^{\dots}$, while there is $2e^{\dots}$. Please check.
* eq. (26) is not correct, there should be (e.g.,) $(c+1)^2$ in the exponent.
Note that these two errors are propagated in many places in the paper.
* the very last paragraph before sec A.1.3: "But then $... > 2e^{-2c^2}...$ there should be no $-$ in the exponent.
* Lemma 5 - the statement is missing $q$ in the perturbation size. The proof is a simple corollary of the previous theorem and In my eyes could be reduced to one short paragraph.
* Why do we often have cases $p \geq 2$? I think it holds when $p \geq 1$; admittedly, I did not pay much attention on the case $1 \leq p \leq 2$ when checking the proofs.
* $p$-norm is norm only when $p\geq 1$. However, you use it for any $p$. Please, mention this fact when introducing $p$-norms.

(Harper 1999) On an isoperimetric problem for Hamming graphs


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$.



If 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).
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.  
Let I_all denotes all possible images that can be represented as described. Each classifier induces a partition of I_all based on predicted labels. 

The 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) -
1) 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). 
The required energy of perturbations vanish in comparison to the expected distance between any two uniformly sampled image from I_all. 

2) 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. 


strength_and_weaknesses: # Strengths : 
1) The analysis appears to be technically sound and best one could seek to establish under this setup.
2) The incorporation of discrete image space via expansion properties of hamming graphs was insightful and could spurn other results. 

# Weakness : 
The 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. 
1) there is an implicit assumption that the union of pre-images of class labels C^{-1}(y) should cover the entire discrete image space. 
2) 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. 

There are implications from these points that weaken the final inference of the stated results. 

- 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 - 

_"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"_

- 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. 

- 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. 

- 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). 

- To summarize, here's a statement from the paper - 

_"Then for most images, a tiny perturbation can make the given image trigger undesired behaviour, ostensibly making the classifier unreliable."_

It 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. 

As 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}. 
Further 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. 


- 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. 


clarity,_quality,_novelty_and_reproducibility: The paper is well written, novel and insightful. 
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies fundamental limits on the Lp robustness of a classifier.
The 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)).
The paper further shows that the result depends on the chosen bit-depth of images.
strength_and_weaknesses: Strengths:
- Interesting and tight result on the robustness of arbitrary classifiers
- The paper is easy to read

Weaknesses:
- Not clear why the focus is on images, as the result seems to apply to arbitrary classification tasks
- 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. 

clarity,_quality,_novelty_and_reproducibility: The paper is generally well written and easy to follow.
Regarding the notation, it isn't clear why inputs are parametrized by a height `n` and an aspect ratio `q` (for images of size n x (nq)), instead of simply considering images of size n x m.

It also isn't clear why the paper focuses on *image* classifiers, when all the results are presented in an generic way that is independent of any specific properties of images.
E.g., wouldn't the same results apply to audio classifiers, or time-series classifiers, or video classifiers, etc?

The role of the "junk class" (if present) could be clarified. As far as I understand, the robustness results hold for any non-junk class. But is there any distinction between perturbations that send an image from a (non-junk) class C1 to the junk class, versus a perturbation that sends an image from a (non-junk)  class C1 to a different (non-junk) class C2? These two types of "adversarial examples" seem qualitatively different.
summary_of_the_review: The main result of the paper seems technically sound, and the approach based on Hamming graphs seems novel and interesting.
The actual interpretation of the result is less clear to me.

When 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.

Sections 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"
Examples 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
It 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)

In light of this, it is not particularly clear how the paper's main result should be interpreted.
Ultimately, 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:
Adversarial 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. 

Weaknesses: 
My 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.
clarity,_quality,_novelty_and_reproducibility: Clarity: the paper is well-written and reasonably clear to follow. The discussion on semantically salient features seems to depart from the largely theoretical theme of the paper however. 

Novelty: The proof techniques are novel and interesting. Robustness impossibility based on isoperimetry-like arguments is not too novel, but the discrete setting is satisfying.

Reproducibility: N/A -- no real empirical results
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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). 

This 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. 

(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)

Therefore, I think this paper is a clear accept. 

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. 

This 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. 

I think the paper can be further improved with the following two aspects: 

1. 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? 

2. 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? 


clarity,_quality,_novelty_and_reproducibility: Clarity: very good. I really enjoyed reading the whole paper, especially the abstract. If possible, maybe the notations in the proof of Theorem 3 can be simplified. I find some of the notations in the proof is not so familiar to me. 

Quality: very good. The proof is clear and rigorous. 

Novelty: very good. As I said, this is something very good to know, but previously I personally never heard of this. 

Reproducibility: good. It's a theory paper, with a very intuitive main theorem. I believe this theorem is correct. 

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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors provide upper bounds on the robustness of an image classifier (images are considered as quantized) and show that there exists a classifier for which this is basically tight. The advantage compared to prior work on this topic by Fawzi et al and Diochnos et al is that there are no distributional assumptions (which can also be seen as a weakness) and that there are results for all $l_p$-balls (including $p=0$).

Strengths:
- novel result on robustness which is shown to be tight
- use of novel proof techniques
- clearly written

Weakness:
- the notion of interesting class as the pre-image set of a classifier is questionable, in particular as the support of true image classes is likely to be concentrated around a low-dimensional structure
- interpretation/discussion of the results could be further improved (even though the authors have improved this during the rebuttal)

All reviewers except one argue for acceptance. I think that this is a nice theoretical result which adds to our understanding of adversarial robustness, in particular also regarding discretization. The practical implications are unclear and the authors are honest about them.

I strongly recommend to the authors to take the comments of the reviewers on the notation and presentation into account. I don't see any reason to keep this notation, in particular as one reviewer pointed out that there is nothing special about images in the construction of the proof. Also the authors should work to make their main result more accessible, in particular the direct connection to Theorem 3 in Harper, 1999 and their "adaptation" should be made clear, that is by citing the original result as it is and then extending it to the stated results using their notation (currently the correspondence is not obvious). Even better would be to give the complete proof, as Theorem 3 is an exercise for the reader in the paper of Harper. 

In the discussion of Section 3.3 the references provided by the reviewers have to be added which discussed similar aspects.
justification_for_why_not_higher_score: Interesting theoretical result but the practical value is limited
justification_for_why_not_lower_score: The result is an interesting contribution on upper bounds on robustness which are shown to be tight.
Decision: Accept: poster