Deep neural networks are known to be vulnerable to small adversarial perturbations in test data. To defend against adversarial attacks, probabilistic classifiers have been proposed as an alternative to deterministic ones. However, literature has conflicting findings on the effectiveness of probabilistic classifiers in comparison to deterministic ones. In this paper, we clarify the role of randomization in building adversarially robust classifiers. Given a base hypothesis set of deterministic classifiers, we show the conditions under which a randomized ensemble outperforms the hypothesis set in adversarial risk, extending previous results. Additionally, we show that for any probabilistic binary classifier (including randomized ensembles), there exists a deterministic classifier that outperforms it. Finally, we give an explicit description of the deterministic hypothesis set that contains such a deterministic classifier for many types of commonly used probabilistic classifiers, i.e. randomized ensembles and parametric/input noise injection.
Paper
Similar papers
Peer review
Summary
The paper investigates randomized classifiers and their robustness against adversarial examples. The authors' contributions can be found along three different axes. First, the authors give the necessary and sufficient conditions so that from a set of deterministic classifiers one can build a randomized classifier that outperforms the best deterministic classifier from the original set (w.r.t. adversarial risk). In sequence the authors present some results in the opposite direction in the binary classification case; e.g., for every randomized ensemble classifier there exists a deterministic weighted ensemble with better adversarial risk. Finally, the authors identify the conditions under which randomization can provably help on a deterministic base hypothesis set. After rebuttal: Upgraded my score from "Weak Accept" to "Accept".
Strengths
Some of the ideas of the paper are building on ideas and findings of prior work by Dbouk and Shanbhag; namely, the observation that a randomized classifier can achieve a decisive advantage over any deterministic classifier, because the adversary can only force a misclassification on a subset of all vulnerable classifiers, where "vulnerable" means classifiers that can be fooled with perturbations of certain magnitude. This observation and the continuation of the work is interesting and the paper is well-written for the largest part, though, near the end I found it more dense than what I would have preferred it to be. I expect this paper to influence to some extent the work that will be done on the robustness of randomized classifiers in the near future. Overall an interesting paper with interesting findings, though, for completeness, I would like to see the authors add some information in the supplementary material even for simple claims; e.g., clearly write down the calculations for Figure 1b, or clarify other small remarks that they have here and there. I also like Section 6; the conclusion that the authors have written -- a clear summary of their contributions and a summary of ideas related to their work that can be explored as future work.
Weaknesses
Figure 1 appears 2 pages after it is first mentioned. One page difference is ok, but two pages is strange. The authors assume that the label y does not change within the perturbation budget $\epsilon$ around $x$. While this is a reasonable assumption, and in fact it is the prevailing assumption in adversarial robustness, nevertheless, it is not the only assumption one can make. Clarifying this and citing any of the following two papers (or both?) so that someone can find more information about the topic, I believe can be important and potentially also motivate further avenues for randomized classification. The two papers are: [M1] Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution https://proceedings.neurips.cc/paper_files/paper/2018/file/3483e5ec0489e5c394b028ec4e81f3e1-Paper.pdf [M2] On the Hardness of Robust Classification https://www.jmlr.org/papers/volume22/20-285/20-285.pdf Line 102: Write down explicitly the adversarial risk of a deterministic classifier in the appendix, if it does not fit in the main part of the paper, so that there is no ambiguity. I think the "Matching Penny" notions are not clearly defined in the paper. It is apparent that some of the ideas have appeared in prior work but the authors spend nearly no time explaining the original ideas and the original context. I believe this should change. In particular, the authors cite two books in lines 168-170 without saying much more; the reader may have no idea about these books and this line of work. It is quite unfortunate that Definition 1 splits between pages because the notation is a bit overloaded and it is clarified on the following page.
Questions
Q1. In lines 144-146 it is stated "Consequently, we get that there always exists a probabilistic classifier that is at least as good as the best deterministic classifier in the BHS $\mathcal{H}_b$." Can you please explain why and how this follows from the previous sentence? Q2. In lines 210-211 we have "Observe that every classifier in $H_b$ is vulnerable at $(x,y) = (0,1)$ and so $R_{\epsilon}(h) = 1$ for all $h\in H_b$". I am not sure I follow; since $x = 0$, then $w^T x = 0$ and therefore 1{$w^Tx < 1$} should return 1, which is really the label $y$. Can you explain?
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
I think the paper is ok in this regard, especially in the light of the clear ideas for future work that one can pursue and are listed in Section 6.
Summary
Several proposed adversarial defenses involve randomized classifiers. Prior theoretical work analyzes both the randomized and non-randomized cases. This paper answers: 1) When does randomization 'help' in adversarial classification? 2) When does it suffice to consider deterministic classifiers? The authors start by describing three common paradigms ( randomized ensemble classifier (REC), weight-noise injection classifier (WNC), input-noise injection classifier (INC)) for constructing randomized classifiers. Subsequently, the authors give a condition describing when randomized classifier over a hypothesis set $\mathcal H_b$ will outperform deterministic classifiers. Next, the authors show that one can always threshhold a binary randomized classifier to get a better performing deterministic classifier. Lastly, the authors show that if $\cH_b$ is all measurable sets, then randomization over $\cH_b$ does not improve the adversarial risk.
Strengths
- The paper answers and important question in the field of adversarial learning: when does randomization help with adversarial classification? - Proofs seem simple and clear
Weaknesses
The exposition is not great. Here are some specific issues. 0. Please state your threat model. Your adversary has access to the randomized classifier, but does not know which random function the learner uses every time a point is classified. 1. Equation 1: $\mathcal R_\epsilon ^y$ is not defined before equation (1) Note that you also need to explain that $\sup_{x'\in B_\e(x)} \ell^{0-1}((x',y),h)$ is measureable. See appendix A of the following reference for this result: Existence and minimax theorems for adversarial surrogate risks in binary classification. N. S. Frank, J. Niles-Weed. 2. Foot note 1: I understand how such a proof would go, but I would expect to see a proof with a maximizing sequence rather than a maximizer in the supplementary material 3. I couldn't understand the argument in line 191-192 4. lines 203-204: I couldn't understand the sentence. "More generally, assumption..." 5. I had a hard time understanding the parallel decision boundaries discussion in example 2 6. line 276: I think an REC built from 2 base classifiers takes on continuously many values. Can you better explain 276-278? 7. The supplementary material is quite disorganized
Questions
- line 108: The Borel sigma algebra is defined in terms of the open sets on a topological space. How are you defining the topology on the set $\mathcal H_b$? It seems that in the REC, ENC, INC paradigms, there is a "continuous" map from $\mathbb R^d$ to $\mathcal H_b$. Perhaps you could use this map. - Can you explain the name "penny matching gap"? - In section 4.1, I would expect that one can always take the threshhold $\alpha=1/2$. Why is this not the case?
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
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
3 good
Presentation
2 fair
Contribution
4 excellent
Limitations
Some of the results only hold in the binary case. The paper discusses this limitation
Summary
This paper provides an analysis of the role of randomization in developing adversarially robust classifiers. It explores the conditions under which randomized ensembles outperform deterministic classifiers regarding adversarial risk. The study also highlights the existence of deterministic classifiers that is at least the same adversarial risk as the probabilistic model, where the authors also connect the theory to weighted ensembles and randomized smoothing. Overall, the paper offers valuable insights into randomization for building robust classifiers in adversarial settings.
Strengths
1. The paper is well-written, ensuring clarity and ease of understanding for readers. 2. The paper offers a foundational understanding of the significance of randomization in building robust models. Especially, I find constructing a probabilistic model from a deterministic model and back particularly interesting. 3. The paper includes an insightful analysis of existing methods (e.g., randomized smoothing ), showcasing their effectiveness.
Weaknesses
1. While the theoretical analysis presented in this paper is intriguing, it leaves me questioning its practical implications in constructing robust classifiers. Specifically, I am concerned about how these theoretical findings translate into practical strategies for building classifiers that perform effectively in real-world scenarios. For example, Theorem 4, in its current form, only addresses the binary case, limiting its applicability. I think the authors can add more discussion on how to guide the future empirical robust model design. 2. The authors show there exists "a probabilistic classifier that is at least as robust as the best deterministic classifier." However, I think it is more important to guide future research to find such a better probabilistic classifier in a principled way. 3. Minor: It is recommended to explain the term "Borel σ-algebra." 4. Minor: Moving the fig1 to near page 4 is better. As I am not an expert in theoretical research, evaluating the novelty and contribution is hard for me.
Questions
1. In adversarial literature, we might consider the attackers can submit malicious input multiple times, where one misclassification is considered a "success attack." I believe the probabilistic model might be more likely to be broken. What happens to the current theorem if considering such an attacking scenario? I found a recent work [1] which is considering this issue. 2. This paper considers a BHS composed of infinitely many linear classifiers. How does the theorem change if BHS is composed of non-linear classifiers? 3. The paper mainly discussed robustness. How does the clean performance change of building a probabilistic model from deterministic models and back? [1] Lucas et al. Randomness in ML Defenses Helps Persistent Attackers and Hinders Evaluators. https://arxiv.org/pdf/2302.13464.pdf
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
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
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors are suggested to include a paragraph discussing the limitations of the paper.
Summary
The paper addresses the theoretical problem of how randomization affects adversarial robustness. It establishes a condition that is both necessary and sufficient for enhancing the robustness of probabilistic models. Furthermore, it proves that in binary classification, a deterministic model can always achieve at least the same level of robustness. The paper also discusses the crucial condition for the effectiveness of randomization. Although the assumptions are strict, the theories in this work can serve as a foundation to further investigate adversarial robustness in probabilistic classifiers.
Strengths
1. The paper is well-written and well-organized. 2. The paper works on an interesting theoretical problem of the effect of using randomization on adversarial robustness. The theoretical result gives a promising hint to better understand the randomization methods.
Weaknesses
1. The theories and proofs in this work heavily rely on binary classifiers with a misleading title. This restricts the practical application of these theories in real randomization scenarios. 2. The work presented lacks in applying and evaluating the theory, even in binary cases. It does not explore the potential of the proposed theory to improve randomization or identify scenarios where a deterministic classifier is possible. For instance, can we find or estimate better deterministic models corresponding to baseline probabilistic classifiers? How can we apply the theories to enhance adversarial robustness? Including quantitative evaluations would significantly improve the quality of the work.
Questions
N.A.
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
See weakness
**measurability issue** That's interesting about measurability! This heart of the issue seems to be showing that a projection of a Borel measurable function is measurable. Under mild assumptions, The projection of a Borel measurable function is measurable with respect to the analytic sigma algebra (which is contained in the universal sigma algebra). The reference [1] includes a variant of this argument for $\mathbb R^d\times S$, where $S\subset \mathbb R^d$. You might also be able to find the fact you need in [6] **further references** Relating to theorem 4.1: Section 5.2 of [7] provides an example of a distribution with 3 classes for which randomized classifiers preform strictly better than deterministic classifiers. [6] Stochastic optimal control: the discrete time case [7] The multimarginal optimal transport formulation of adverarial multiclass classification
Thanks again for the useful references
We would like to thank you for pointing out these useful references. After reading [6], we found that another way of ensuring the Borel-measurability of the projections would be to satisfy [6, Proposition 7.14]. We would need $\mathcal{X}$ to be a Borel space and $\mathcal{Y}$ a product of Borel spaces (already satisfied), and this would yield that Borel-measurability of $h: \mathcal{X} \to \mathcal{Y} \subset \mathbb{R}^K$ is enough to ensure measurability of individual components $h_y$. These assumptions are simpler and close to the settings that are used in practice. With respect to the Example in [7, Section 5.2], we find it fascinating and closely related to our setting. Thank you for pointing it out. In their case 4-i authors show that a randomized classifier that assigns $\frac{1}{2}$ to every "conflicting" point or region is a saddle point. This is closely related to the Nash equilibrium in the original game of matching pennies. Indeed, if one restricts to a pair of points, there is a matching pennies game going on: authors say "The adversary gathers classes as much as possible and distributes them as uniform as possible". That is, at each point $\bar{x}_{ij}$ there is the same probability that this point came from class $i$ and $j$, then the equilibrium strategy is to predict uniformly at random between class $i$ and $j$. It is also interesting that the optimal randomized classifier in this example (weak partition, page 39 of [7], bottom) can be built as a uniform mixture of 6 deterministic ones $f_{ijk}$ that predict $i$ in $B\_{\epsilon}(x_i)$, $j$ in $B\_{\epsilon}(x_j) \setminus B\_{\epsilon}(x_i)$ and $k$ in $B\_{\epsilon}(x_k) \setminus (B\_{\epsilon}(x_i) \cup B\_{\epsilon}(x_j))$. Each $f\_{ijk}$ has standard power of 1, and adversarial power of $w_i$ against an optimal attack, like the constant classifiers. However, the uniform mixture of these 6 classifiers would have standard power of 1, and adversarial power of 0.5, meaning an increase in performance of $0.5 - w_1 \gt 0$. One can compute the matching penny gap of this mixture of 6 classifiers in this dataset, and conclude it is $\frac{1}{6}$. The average risk is $\frac{2}{3}$, and the risk of the mixture is $\frac{2}{3} - \frac{1}{6} = \frac{1}{2}$. Lastly, this example shows that Theorem 4.1 does not hold in multiclass! Indeed, authors show that their randomized classifier is an equilibrium, and that "In fact, it is unavoidable to introduce weak partitions". They further say that "In other words, even this simple discrete measures, it is necessary to extend strong partition to weak partition in order to achieve the minimax value". We will definitely add this important remark in the paper. The conclusion would therefore be that in the multiclass setting, there exist data distributions for which randomization is necessary, proving an even stronger point for randomization for adversarial robustness. Understanding these situations would be an interest avenue of future work, because as the authors say, it "depends on both the geometry of data distributions and their magnitudes" and even with discrete toy examples, there are non-trivial situations. **Answers to other questions** > Parallel decision boundaries To simplify the example, consider $A = \\{0\\} \subset \mathbb{R}$ and the parallel classifiers $h_r = A \oplus B_r(0)$ of the form $h_r(x) = \mathcal{1}\\{ x \in (-r, r) \\}$ for $r > 0$.. Recall that a matching penny configuration for two classifiers arises when 1) **both are vulnerable**, but 2) **not simultaneously**. We will see that this cannot arrive with this family of classifiers that are "parallel". W.l.o.g, take any point $x > 0$ and suppose it is of class is 0. Take any two classifiers $h\_{r_1}, h\_{r_2}$ with $r_1 < r_2$ and fix the attacker budget to $\epsilon$. Note that $h_{r_1}$ is vulnerable at $x$ if an only if $x - \epsilon \le r_1$. That is, the attacker must be able to move $x$ inside $(-r_1, r_1)$ with its budget of $\epsilon$. This also holds for $h_{r_2}$. To satisfy condition 1), we must ensure that $x - \epsilon \le r_1$ and $x - \epsilon \le r_2$. However, any $x$ that satisfies $x - \epsilon \le r_1$ immediately satisfies $x - \epsilon \le r_2$, as $r_1 < r_2$, meaning that the same perturbation induces an error on both classifiers. In conclusion, if condition 1) is satisfied, 2) cannot be. For the case of general parallel sets $A^{r_1}, A^{r_2}$, note that if $r_1 < r_2$ then $A^{r_1} \subset A^{r_2}$. Then the argument is similar to the example above.
Interesting! That's a good resolution to the measurability issue. I will keep my score and vote for acceptance.
Thank the authors for the rebuttal. I appreciate the detailed explanation. I hope the authors can incorporate discussion in the rebuttal to improve the paper. It is encouraged to mention [1] and discuss the differences and similarities. I think this can make the paper to be accessed by more audiences. I increase my score to 7. [1] Lucas et al. Randomness in ML Defenses Helps Persistent Attackers and Hinders Evaluators.
Thank you
We are very honoured by your appreciation or our paper. We forgot to include it explicitly in our first answer, but indeed we will be including the discussion about the threat model considered in our work. Here we will discuss [1], as it shows that the role of randomization can change depending on the chosen threat model and the hypothesis about the attacker's capabilities.
Thank you for the responses
I have read the other reviews as well as the response that the authors have provided to the various issues that were raised in the reviews and I am happy with the explanations. I can see that the paper will have more clarity and better content overall in the end and I will upgrade my vote from "Weak Accept" to "Accept". Thank you for a very interesting paper!
Thank you
We are very glad that our response has made the paper clearer. We thank you for your upgrade !
Thank you for your response. It has addressed all of my concerns, and the work has the potential for further investigation. I will increase my score to 6.
Decision
Accept (spotlight)