Finding classifiers robust to adversarial examples is critical for their safe deployment. Determining the robustness of the best possible classifier under a given threat model for a given data distribution and comparing it to that achieved by state-of-the-art training methods is thus an important diagnostic tool. In this paper, we find achievable information-theoretic lower bounds on loss in the presence of a test-time attacker for multi-class classifiers on any discrete dataset. We provide a general framework for finding the optimal 0-1 loss that revolves around the construction of a conflict hypergraph from the data and adversarial constraints. We further define other variants of the attacker-classifier game that determine the range of the optimal loss more efficiently than the full-fledged hypergraph construction. Our evaluation shows, for the first time, an analysis of the gap to optimal robustness for classifiers in the multi-class setting on benchmark datasets.
Paper
Similar papers
Peer review
Summary
The paper generalizes lower bounds on the adversarially robust error on a finite dataset from binary to multi-class classification.
Strengths
1. The paper is well presented and easy to read, which is no mean feat for the amount of theory that is introduced and developed. 2. The formalization and assumptions are clearly stated, well arranged, and do not contain unnecessary complications. 3. The developed theory is correct as far as I can tell. 4. The experimental evaluations make sense for the discussed topic, regard standard baselines and are easy to understand. They are shown even while they don't support the necessity of the multi-class theory, which is nice to see. 5. The fact that calculating the bounds based on binary l2-ball intersections makes no difference in practice doesn't mean that the theory is not helpful for estimations that are in principle more correct. 6. Limitations are discussed honestly. 7. The code looks nice, but I haven't tested it.
Weaknesses
1. While they are no clear weaknesses, there are some points unclear to me which I list below in the Questions section and I would much appreciate to see answered and in some cases discussed in the paper. 2. A substantial part of the formalization, theory and experimental design are not completely newly developed, but carried over from the previous paper "Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries" which deals with the same problem in the more special case of binary classification. This is why I'm rating this submission currently as a standard "accept".
Questions
1. While Equation (1) is true, I think it is not trivial, but a theorem that depends on some assumptions (which appear to be fulfilled by the considered hypothesis classes). It was proven in (Pydi,Jog 2022: "The Many Faces of Adversarial Risk")[https://arxiv.org/abs/2201.08956], but there might be earlier, more well known versions of the theorem. I think the intuition why (1) is true should be given. 2. l. 89 I think it should better read "the vector of _robustly_ correct classification" 3. l. 97 Should "feasible" read "achievable" here to stay consistent? 4. l. 97 Do the nonnegative linear combinations need to have factors that sum to less than 1? 5. Is L without * correct in Eq. (2)? If so, it wasn't defined. 6. l. 122 missing word 7. l. 124 extra ( 8. Is the construction of the full hypergraph indeed computationally expensive for an l2 threat model? Intutitively, the geometry might make incidence matrix very sparse and its computation quite straightforward. Or is it rather an issue with the LP solver? 9. Would it make sense to regard the reverse truncation where if we find a triple of pairs with overlap (as in Fig. 1 left), we assume that there is also a point that generates the degree 3 hyperedge (and so on for higher degrees)? this might maybe yield an upper bound on $L^*(K)$. 10. l. 296 whether and in which sense the hypothesis class is much smaller is not obvious, and it is not clear if insufficient fitting within the class might be responsible for a large part of the gap. 11. In Figure 3, an empirical model evaluation as in Figure 2 should be included. ($L_{CW}$ is a bit confusing at first look, since many papers use that for Carlini-Wagner l2 attacks.) 12. Why not use the full AutoAttack? 13. The statistics on number of hyperedges should be included for all datasets, and a few values of epsilon (including 2 and 2.5), since they quantify the importance of regarding multi-class overlaps. 14. Also statistics like the average distance of an image to the closest one from another class would be nice to understand the geometry of the neighborhood overlaps. 15. It would be great if the authors could find a type of dataset and threat model where multi-class neighborhood overlap plays a bigger role than with MNIST and CIFAR. Maybe even a toy example would be illustrative. 16. Since the paper talks about optimal errors for finite distributions, it would make sense to show evaluations both on training and test sets. 17. A more concrete comparison to Trillos et al.[21], if applicable with evaluation numbers, would be helpful. 18. A discussion of the limitation to distributions with finite support and whether one can expect this assumption to be softened in future works building on this one would be interesting.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
The limitations are discussed in detail.
Summary
Deep learning techniques achieve state-of-the art performance on various classification tasks, but alarmingly, they are highly susceptible to adversarial perturbations. It is currently unknown whether there even exist classifiers that achieve low adversarial training risk on standard datasets. This paper aims to close this gap. The authors restate the adversarial learning problem over all classifiers as a linear program which can then be solved using standard LP techniques. This LP is stated in terms of the hyperedges of a hypergraph. As the resulting LP is computationally intractable, the authors then propose several ways to truncate this LP. The paper concludes with an experimental section in which they use the paper's techniques to upper bound the minimal possible adversarial loss for MNIST and CIFAR-10.
Strengths
- It is currently unknown if finding robust classifiers to real-world datasets is possible. This paper presents a strong argument that such classifiers exist - Using linear programming to attack this problem is very creative!
Weaknesses
- I have some concerns about the correctness of this paper. Here are some specific issues 1. $q$ in line 20 of the supplementary material is not defined. This makes it quite hard to evaluate the correctness of the proof of Lemmas 1 and 2 2. I suspect Lemma 1 is false. Lower bounds on the adversarial risk computed in this paper rely on this lemma, so if Lemma 1 is false, these bounds would be invalidated. Consider the following example: Consider 3 vertices with the incidence hypergraph of the left picture in Figure 1. Specifically, $\mathcal N(u)= \{u,v\},\mathcal N(v)=\{v,w\}, \mathcal N(w)=\{w,v\}$. Then the incidence matrix $B$ is | |$u$|$v$|$w$| |------------|-----|----|----| |$e_{wu}$| 1 | 0 |1 | |$e_{uv}$|1 | 1 |0| |$e_{vw}$| 0 | 1 |1 | |$e_{u}$ |1 | 0 |0 | |$e_{v}$ |0 |0 |1 | |$e_{w}$ |0 |1 |0| Consider the vector $b= [0.5, 0.3, 0.2]$ (with vertices in order $u$, $v$, $w$). This vector clearly satisfies $b\geq 0$ and $Bb \leq \mathbf 1$. We will now show that this vector is not in $\mathcal P_{\mathcal V, N,\mathcal H}$, as defined in line 96 of the paper. For contradiction, assume that there is an $h$ for which $q_N(h)$ satisfies $0\leq b_i\leq q_N(h)_i$ for $i\in \{u,v,w\}$. By definition, $q_N(h)_v=\inf$ { $h(x): x\in N(v)$}. Thus $h(u)\geq .5$ and $h(v)\geq .5$. As $h$ is a probability vector, it follows that $h=(.5, .5, 0)$ and $q_N(h)=(.5,0,0)$. This is a contradiction as $h(v)\leq b(v)=.3$. 3. In definition 2, h is defined to be $\cY$-valued but the expression $1-h(\tilde x,c)_y$ assumes that this function is $\mathbb R$ valued. As this definition is central to section 3, the correctness of this section is hard to evaluate - The paper does not introduce central mathematical concepts or introduces them poorly. For instance, 1. line 82: "architecture" is discussed before neural nets are introduced 2. what is 'downwards-closed' in line 110? 3. The phrase "correct probability vectors" in Lemma 1 is misleading because the q's typically don't sum to 1 4. What does 'fractional coverings' mean in line 119? 5. lines 241-246: an argument is presented involving the fractional vertex packing polytope and the independent set polytope but these are only introduced very briefly
Questions
- Can you explain the issues with Lemma 1 pointed in in the first bullet under weaknesses? Resolving this issue would convince me to change the review score - Problems in optimal transport frequently need to solve linear programs in $\mathbf q$ with the constraint $\mathbf q\geq 0$. For computational expediency, the sinkhorn algorithm uses entropic regularization to deal with this constraint. Could you possibly make use of this technique? - It seems that in the matrix inequality $Bq\leq 1$ in Lemma 1, many rows may be linearly dependent. Have you tried getting rid of such rows?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
1 poor
Contribution
3 good
Limitations
One central limitation of this work is that it studies the minimal possible adversarial risk over all possible (soft) classifiers rather than a particular function class. This limitation is discussed in the paper.
Summary
This work proposes to theoretically evaluate the robustness of a multi-class classifier by setting the lower and upper bounds of the optimal loss, i,e, the lowest loss achievable for a given hypothesis family. The lower bound is established by extending the conflict graph-based framework previously applied to the binary classification setting. The upper bound is built by generalizing the Caro-Wei bound. Beyond theoretical analysis, this work also focuses on computable methods to estimate the bounds, i.e. using the lower bounds of binary classification problems to compute that for the multi-class problem.
Strengths
It is an important contribution to set up an upper and lower bound for the lowest achievable classification loss under the testing-time perturbation. These two bounds help to narrow down the possible range of the classification loss facing input noise, which measures accurately the robustness of a classifier. Furthermore, this work provides the link between the optimal loss bound of binary classification tasks and that for multi-class tasks. This contribution enables efficient computation of the bound estimates when the number of classes increases.
Weaknesses
I have to admit that I am not familiar with this theory. It takes me quite some time to read the contexts before I can figure out how this framework can be integrated into the investigated problem. I think for any readers / reviewers without the background information, offering even a brief introduction could be very helpful to evaluate the contribution.
Questions
How tight are the upper and lower bound ? Especially for the upper bound, this is established based the Caro-Wei bound, which is different from the conflict hypergraph framework. It is not clear how accurate the upper bound could be.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
None
Summary
This paper aims to analyze the optimal 0/1 loss under the most strongest test time attack. The study commences by formulating the problem of obtaining the optimal classifier (based on 0/1 loss) as a linear program on a graph. Subsequently, the authors address the high computational complexity of calculating the optimal 0/1 loss by proposing a reduction technique through graph truncation. This reduction enables the computation of a lower bound of the 0/1 loss in a feasible timeframe. Ultimately, the authors present empirical evidence comparing their bound with the empirical defense method on real-world data. Notably, they discover that the widely-used baseline (adversarial training) still offers significant potential for improvement.
Strengths
- The paper is written clearly and easy to follow. - This paper extents the analysis on the optimal classifier under test time attack to multi-class classification setting. It seems to be a decent extension/contribution to the theoretical side of the field of adversarial robustness. - Usually for this kind of problem, the computation complexity is one of the main challenge. However, they are able to find a way to speed it up. The idea of reducing it to a graph and then truncate the complex edges to reduce the computation needed for getting the bounds is interesting. In addition, they also show that empirically, such relaxation does not lose much information.
Weaknesses
- Although it is mentioned in the related work that this is different from verifying robustness. I think it would be a valuable information to include bounds for verified classifiers in the empirical section. It would be interesting to see how close the existing verified classifiers are to the optimal bound. - A related work titled "Robustness for non-parametric classification: A generic attack and defense." published in International Conference on Artificial Intelligence and Statistics, 2020 can be added. This work also utilize the idea of creating graph with the vertices being each example and edges being conflicting examples pairs. They tried to approach the optimal 0/1 by removing minimum number of edges. Although they did not compute specific bounds on the optimal 0/1 loss, I think it is still worth being discussed. - This is a work with solid technical contribution. However, as mentioned in the limitation, the lack of implication on how to close the gap between the current robust classifiers and the optimal classifier limits the impact of this work to a moderate-to-high impact paper. - Although a method for speeding up the algorithm through truncating the graph is proposed, the applicability of the proposed algorithm in practice seems to be still limited in practice due to heavy computational cost (in the experiment, only three class classification problems are run).
Questions
Are there any of my review comments that misunderstood the paper? If so, please point them out. I am happy to adjust accordingly.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors do properly addressed the limitation of this work, which includes the lack of scalability of their algorithm and the lack of implications on how to close the gap between the current robust classifiers and the optimal classifier.
1. I'm convinced by your explanation, I misunderstood the role of $h$. I am updating my score. Consider including a proof outline of Lemma 1 in the main text of the paper, to further explain why this lemma would be true. Overall, I had a hard time with the exposition and organization of the technical portions of this paper. From the text, it is difficult to understand why the mathematical claims are true, (and sometimes also what they mean). 2. Your responses to these two questions helped me understand your approach. Consider including these discussions somewhere in your paper
Thank you for your quick response. We are happy that you are convinced about the correctness of Lemma 1. We also appreciate your suggestions on adding a proof outline of Lemma 1 in the main text and adding discussions of the 2 questions to the paper. Currently, due to space constraints we are unable to add a proof outline, but we plan on incorporating the discussion of the 2 questions into the Appendix of the camera-ready paper. On your comment about some mathematical claims being unclear, could you please elaborate on which claims you are referring to? We are happy to clarify these points during the discussion period.
Here are a handful of examples of text I had a hard time understanding. - line 82: "architecture" is discussed before neural nets are introduced -line 119: "fractional coverings" are not introduced - lines 242-243: "fractional vertex polytope", "independent set polytope" - line 251: "the conflict hypergraph is hereditary" - line 261: "Cari-Wei bound"-- if this concept is important enough to title a section, I would expect an introduction and discussion of this result -line 274: "In general, Lemma 4 can be thought of as a randomized procedure for rounding an arbitrary vector....". I'm not entirely sure what this means, or where rounding takes place in Lemma 4 A lot of this is due to not defining technical mathematical terms. I would expect NeurIps submissions to clearly introduce mathematical concepts that are not well known in the ML community, even if they are standard within graph theory.
Thank you for the feedback on improving paper clarity. Due to space constraints, it is difficult to incorporate an introduction of all concepts into the main paper, but we will add additional discussion of graph theory concepts and Caro-Wei bound into the Appendix. We note that these graph theory concepts are not critical to the main contributions of the paper, but are present in discussions to give a graph theory interpretation. We elaborate on the points you raised below: > line 82: "architecture" is discussed before neural nets are introduced By architecture, we mean a function class in which each function is specified by a finite number of parameters. This encompasses neural networks but is more general. We will update the wording in this portion to reflect this idea more clearly. > line 119: "fractional coverings" are not introduced A fractional covering is a nonnegative weighting $z$ of the hyperedges such that each vertex receives coverage at least its vertex weight. I.e. the sum of the weights of the hyperedges containing $v$ is at least the weight of $v$: $B^Tz \geq p$. We will add a textbook reference and further discussion in the Appendix. > lines 242-243: "fractional vertex polytope", "independent set polytope" We currently state the definitions of these polytopes briefly, although we are not explicit that both are subsets of $\mathbb{R}^{\mathcal{V}}$ just like $\mathcal{P}_{\mathcal{V},N,\mathcal{H}}$ is. We will write more explicit versions of these definitions and add a textbook reference. > line 251: "the conflict hypergraph is hereditary" By hereditary, we mean that the edge set of the conflict hypergraph is downward-closed (ie. if $e \in \mathcal{E}$ and $e' \subseteq e$, then $e' \in \mathcal{E}$). We will update the text to add a definition of downward-closed in line 110 where it is first mentioned, and then change line 251 to state “edge set of the conflict hypergraph is downward-closed” instead of “conflict hypergraph is hereditary” for consistency. > line 261: "Cari-Wei bound"-- if this concept is important enough to title a section, I would expect an introduction and discussion of this result We will add further discussion of the Caro-Wei bound to this section. The original Caro-Wei lower bound on cardinality of the maximum independent set in a graph can be recovered by taking both w and p to be vectors of all ones. In this case, $((A+I)1)_v$ is one plus the degree of v. > line 274: "In general, Lemma 4 can be thought of as a randomized procedure for rounding an arbitrary vector....". I'm not entirely sure what this means, or where rounding takes place in Lemma 4 Thank you for pointing this out, the sentence should say “the proof of Lemma 4 can be thought of as …”. We will update the text to fix this.
Thank you for responding to my concerns and questions.
After reading the responses, I still hold my original opinion that this is a technical solid paper and it can bring moderate-to-high impact on the development of theories for adversarial robustness. Therefore, I would like to maintain my original score.
Response to Rebuttal
Thanks a lot for the detailed and insightful response! The additionally provided explanations and numbers are very helpful. I believe this is a strong contribution and am raising my score from 7 to 8. --- > 9. I personally would find upper bounds on the optimal lower bound very interesting, as they also enable judging the tightness of the lower bounds. I'd leave it to your judgement of the interestingness of these upper bounds and the actual numbers that can be calculated. > 16. (/15. evaluations both on training and test sets.) What I originally meant here was the question how close the AT model comes to the lower bounds on the training set. I think it would be interesting how much of a gap in training error could still be optimized away (if we consider the lower bounds to be close to the maximal lower bound) by better (or more overfitting) AT schemes, train attacks and models.
Decision
Accept (spotlight)