Are Probabilistic Robust Accuracy Bounded

We thank the reviewer for the time and effort in working on the review and for the kind words on our work. We carefully address the concerns as follows. If any concerns still persist, we are more than happy to discuss them and edit our paper accordingly.

Regarding the comment: “W1: The experimental setup is on the light side. SVHN, CIFAR-100, TinyImageNet (and similar datasets) would be appreciated. This experimental setup mirrors existing work, so I don't think this is a reason for rejection but, it would be useful to see this validated across a more diverse set of datasets.

The range of $\kappa$ values shown leaves out valuable insights into values $\ll 1$. I would suggest, e.g. to replicate Figure 3 with logscale x axis, e.g. starting with 1e-5. How do the Bayes errors compare for such small $\kappa$? How does the prob. robust classifier bound approach the bound of the deterministic classifier when $\kappa\to 0$? I would suggest the authors include more $\kappa$ values in this work and more datasets/architectures in a revision or future works section.”

Great suggestion. We have now managed to extend the experimental evaluation to the suggested datasets. The upper bound of probabilistic robust accuracy and the state-of-the-art performance of SVHN and TinyImageNet are shown in the following table. CIFAR-100 is still running, and we are happy to add the results in our final version.

Thank you for pointing this out! As you suggested, the change of the upper bound of probabilistic robust accuracy against the growth of $\kappa$ is shown in log-scaled $\kappa$ in Figure 6 in the revised version (Section C). Also, we are happy to include it in the main body if needed.

Regarding the comment: “W2: L176-190 (in particular L186-L188) are hard to follow when not familiar with Zhang & Sun's work. A more detailed explanation would be appreciated. For instance, the authors could keep it short in the main body but add a short Appendix with more details.”

Thanks for the suggestion. We have added Appendix D in the revised version to help with understanding.

Regarding the comment: W3 and minor

Thanks for pointing them out. We have fixed them in the revised version and added abbreviations in Line 216 and Line 232 to denote the subscripts of Eq (9) and Eq (11).

We thank the reviewer for the valuable comments and questions. Our response to each question is provided in turn below.

Regarding the comment: “Could you clarify the choice of vicinity used in the experiments? If I understood correctly, the vicinity is defined using the $L^\infty$ -norm. Are there other common choices for defining vicinity, and could evaluations be conducted with those as well?”

Thanks for your constructive comments. Indeed, we use the $L^\infty$-norm in our experiment. $L^2$-norm is also a common choice for defining vicinity and the evaluation can be conducted with $L^2$ and other vicinities as well. Similar to the $L^\infty$ case where the ratio of vicinity shrinking is $(1 − \sqrt{2\kappa})$ in two dimensions, the ratio for an $L^2$ in two dimensions will be the solution of $\arccos(\text{ratio} ) = \kappa\pi + \sqrt{1 - \text{ratio} ^2}.$ In higher dimensions, it will look like a spherical cap. For other shapes of vicinities, we may also derive the effective radii according to Theorem 3.4, though the specific forms may vary.

Regarding the comment: “How do the upper and lower bounds in this work relate to the concept of certified radius, which is a significant measure of robustness in various probabilistic robustness methods, such as Randomized Smoothing?”

That would be a really interesting and insightful question to discuss. The following might not be a solid theoretical answer, as we need to properly work out the answer. Intuitively and in my personal opinion, in the optimal condition of the probabilistic robustness, we will know that those points with probabilistic robustness will also have a vicinity for deterministic robustness. If we assume the optimal probabilistic robust accuracy is $a$ for some distribution given $\epsilon$, then we can conservatively assume that those $1-a$ points are not guaranteed with deterministic robustness and their radii are 0. If we conservatively assume that no points earn a larger certified radius. As a result, we will know that the certified robustness in terms of the radius notion (the one you suggested) would most likely be lower bounded by $(a\epsilon(1 - (2\kappa)^{\frac{1}{n}}))$

Thank you for your insightful review and feedback. We hope to address your concerns and answer your questions below:

Regarding the comment: “W1.The analysis largely inherits the notion and methodology from [Zhang and Sun, CAV 2024]. Technical novelty is not very significant.”

Thank you for your comments. We would like to clarify that our work is much more than merely applying the same analysis from [Zhang and Sun, CAV 2024] to a different metric.

First, the task in this study can be more challenging. Due to the difference between the definition of deterministic robustness and probabilistic robustness, establishing an upper bound for probabilistic robustness requires knowing the proportion of adversarial examples, which demands quantitative analysis in each vicinity and makes probabilistic robustness more difficult to analyze theoretically.

Second, the method that we used to establish the upper bound is different. [Zhang and Sun, CAV 2024] used convolution to establish the upper bound of deterministic robust accuracy. In contrast, we primarily adopt directional derivative (e.g., Theorem 3.4, Corollary 3.5) and higher-dimensional geometry (e.g., Theorem 3.4, Corollary 3.6).

Thirdly, we establish more than just the upper bound for probabilistic robustness. We quantitatively give the vicinity size of deterministic robustness that probabilistic robustness can ensure in the optimal condition. Particularly, this connection, denoted by $\epsilon(1 - (2\kappa)^{\frac{1}{n}})$ in Corollary 3.6) explains why even a small $\kappa$ can lead to high probabilistic robust accuracy.

Regarding the comment: “The presentation can be made more self-contained: (1) It would be good to show the formal definition of deterministic robustness and how the Bayes optimal classifier is derived in Eqn. (7). (2) It would be good to explain how the direct method from Ishida et al can be used to compute the Bayes error of real-world datasets.”

Thanks for the constructive comment and we will revise the draft accordingly. In particular, the following definition of deterministic robustness has been added in the draft as Eq (1). $P_{(\mathbf{x}, \mathbf{y})\sim D} ((h(\mathbf{x}) = \textnormal{y}) ) \land \forall\boldsymbol{x'}\in\mathbb{V}(\mathbf{x}).~ h(\boldsymbol{x'}) = h(\mathbf{x}) )$

We have also added a brief introduction to the derivation of [Zhang and Sun, CAV 2024] in Appendix D and how to the derivation from [Ishida et al. 2023] in C.1.

Regarding the comment: “Line 350: vicninty -> vicinity”

Thanks for pointing that out. We have fixed it in the revised version.

Regarding the comment: “Figure 2: what do $b_a$, $b_p$, $b_d$ mean? Some explanation preferred.”

We will expand the caption of Figure 2 to make it clear: “Comparing the SOTA classifier performance with upper bounds, i.e., 1 - the Bayes error of vanilla accuracy ($b_a$), probabilistic robust accuracy ($b_p$), and deterministic robust accuracy ($b_d$).”

Regarding the comment: “Line 364, why does "$n$ grows" make the probabilistic robust accuracy higher? In my understanding, with larger dimensionality, achieving the robustness under the same Linf radius would become harder.”

Thanks for your constructive questions. We agree that a large $n$ often correlates to lower deterministic robustness. Yet, according to $\epsilon(1 - (2\kappa)^{\frac{1}{n}})$ in Corollary 3.6, we show that when the vicinity size for probabilistic robustness is fixed and $n$ grows, the size of vicinity size in which deterministic robustness is guaranteed drops quickly. This is a reverse effect of the curse of dimensionality. Intuitively, since guaranteeing deterministic robustness in a much smaller vicinity is easier, the presented upper bound of probabilistic robust accuracy likely grows.

Once again, we thank Reviewer for the time and effort in helping improve our paper. Should further clarification be required, feel free to ask, and we would be happy to respond.

Regarding the comment: “Since Bayes error refers to the minimum achievable error for any classifier on a given problem, does this imply that it is merely a theoretical assumption and that training a true Bayes classifier may be impractical? If so, does this mean that the derived bound serves primarily as an analytical perspective on robustness rather than offering practical experimental guidance?”

Thank you for your comments. Kindly find our response as follows.

First, in many situations, approaching the Bayes classifier is practically possible. The work of Ishida et al. [2023] shows that many image classifiers have already achieved an accuracy very close to the upper bound.

Second, as discussed above, even if it is challenging to develop a true Bayes classifier, knowing the upper bound is still beneficial in many ways. In brief, as discussed by Varshney et al. [2020], Theisen et al. [2021], and Ishida et al. [2023], an upper limit can practically be a reference for the performance of a new solution.

Lastly, as discussed earlier in the first answer, while our derived bound primarily serves as an analytical perspective on robustness, the derivations and findings (e.g., Theorem 3.2) may still offer practical experimental guidance. This could aid both potentially improving robustness and deciding the kappa value according to the specific security requirements.

Lav R. Varshney. “Addressing Difference in Orientation toward Competition by Bringing Fundamental Limits to AI Challenges”. In: NeurIPS workshop, ML Competitions at the Grassroots (CiML 2020). Dec. 2020.

Ishida, T., Yamane, I., Charoenphakdee, N., Niu, G., & Sugiyama, M. Is the Performance of My Deep Network Too Good to Be True? A Direct Approach to Estimating the Bayes Error in Binary Classification. In The Eleventh International Conference on Learning Representations.

Theisen, R., Wang, H., Varshney, L. R., Xiong, C., & Socher, R. (2021). Evaluating state-of-the-art classification models against bayes optimality. Advances in Neural Information Processing Systems, 34, 9367-9377.

We thank the reviewer for the thoughtful feedback and valuable suggestions.

Regarding: “The primary concern is that the problem addressed in this paper lacks significance, which in my opinion limits its acceptance. The main contribution is the derivation of certified accuracy bound from a Bayes perspective, but the paper does not provide effective insights into improving model robustness—a key focus in this field. Although the authors propose a robustness error bound through the lens of Bayes Error, they do not attempt to use this perspective to develop a method that could enhance model robustness, which remains the core issue in this area.”

Thank you for your comments. We believe our work is significant for the following reasons.

• Our work provides the first method to compute the upper bound for probabilistic robust accuracy. Knowing the upper limit is beneficial in many ways, e.g., it provides a way of measuring whether a certain technique has reached the optimal performance, or whether a method is too good to be true (if its performance is beyond the upper bound) [Ishida et al, 2023]. Also, a well-derived upper bound helps evaluate a new solution, as an alternative to the relative evaluation against current best solutions [Theisen et al., 2021].

• Our work indeed also provides guidelines on how to design practical methods for improving robustness. Specifically, Theorem 3.2 establishes that under the optimal condition for probabilistic robustness, each prediction matches the majority prediction in the vicinity. This suggests that a practical method for probabilistic robustness should probably consider voting during inference. We empirically verify this in the first research question in the experiment. (Line 427, does voting always increase probabilistic robust accuracy empirically?)

• Our work also contributes to the understanding of probabilistic robustness. We derive, in the optimal case of probabilistic robustness, how much deterministic robustness will be simultaneously guaranteed. This builds a formal link between probabilistic robustness and deterministic robustness and lays the groundwork for future theoretical and practical research on robustness. We show that a small relaxation in $\kappa$ may bring a large relaxation in effective vicinity size where deterministic robustness is guaranteed. In practice, this may help a user choose $\kappa$, or choose whether to adopt probabilistic robustness, according to the specific security requirements.

Regarding the comment: "The conclusions regarding the bound are not particularly surprising. Given that randomized smoothing allows for bound failure, the probabilistic robust accuracy is inherently higher than deterministic robust accuracy, rendering this result somewhat expected."

Thank you for your comments. We agree that the qualitative relationship between the upper bounds of deterministic robust accuracy and probabilistic robust accuracy might be expected indeed. To actually derive a quantitative relationship is however much more challenging. Our work makes it possible to answer questions such as what is the exact upper bound of probabilistic robust accuracy, and how the tolerance level kappa affects the upper bound. Furthermore, we are able to precisely explain why the upper bound of probabilistic robust accuracy is much higher than that of deterministic robust accuracy, i.e., a non-zero kappa would cause the effective vicinity size to shrink exponentially, especially when dimension n is large, as shown in $\epsilon(1 - (2\kappa)^{\frac{1}{n}})$.

Thank you for the clarification and sorry for the late response. After reassessing the contributions of the paper, I find that the proofs do not seem to involve significant challenges, which makes it difficult to justify the paper’s acceptance. To better understand the contributions of the paper, could you clarify what specific challenges have been addressed in this work and where the difficulties in the proofs?

1. Lemma 3.3: Since $\mu_k(x)$ (Eq. (14)) represents a probability, the shift $\mu_k(x+\phi \hat{\phi}) - \mu_k(x)$ naturally relates to the integral of the changes in the PDF after shifting (Eq. (42)). The proof of Lemma 3.3 appears to involve straightforward computations regarding probabilities based on Eq. (42) and does not seem to present significant challenges. Could you explain where the difficulty lies?

2. Theorem 3.4: The paper attempts to show that deterministic robustness is a weaker condition than probabilistic robustness. This conclusion appears evident, as probabilistic robustness inherently allows for an error $\kappa$, making it a more relaxed condition. As stated on line 362, "with a much smaller vicinity," the proof also seems straightforward, relying on $\phi_1$ and $\phi_2$. Could you clarify what makes this proof challenging? Additionally, demonstrating the tightness of the bound would enhance its value.

3. Corollary 3.5: What is the motivation behind this corollary? I did not find it directly used in the following proofs. Why is it necessary to analyze the case where $\delta \to 0$?

4. Theorem 3.7: This theorem appears to rely heavily on Zhang & Sun (2024) and seems to address the same conclusion as Theorem 3.4, namely that deterministic robustness results in a smaller vicinity. Could you clarify if there are significant differences between the two results?

5. Corollary 3.8: Similar to Theorem 3.4, this result also seems evident, as deterministic robustness is inherently a weaker condition than probabilistic robustness. The proof appears similar to that of Theorem 3.2, which involves analyzing monotonicity w.r.t. $\kappa$ based on error differences $e(\kappa_1)-e(\kappa_2)$. Could you explain the novelty or challenges in this result?

6. Experiment: Regarding the code in “Training for probabilistic robustness.ipynb”, what is 305 in the line:

x__ = x_.repeat(305, 1, 1, 1)  

7. Based on line 1227, the Bayes error calculated in this paper seems to rely directly on the algorithm from Ishida et al. Does the paper propose a new method for estimating the Bayes bound, or is it dependent on existing work?

8. According to the code, the voting mentioned in the paper involves adding uniform noise to the input $x$ to enhance the model's robustness. This idea is the same as randomized smoothing (Cohen et al., 2019), which is essentially a majority voting scheme, except that RS uses Gaussian noise. There has been extensive research on RS. Could you clarify the setting used in this paper for comparison with RS? Does the RS baseline include adding Gaussian noise? Or is Gaussian noise added first, followed by uniform noise?

9. In my understanding, what should theoretically be bounded is the probabilistic certified robust accuracy. Why is it that the baseline methods DA and CVaR, as provided in their original papers, only report empirical robust accuracy rather than certified robust accuracy? These two methods appear to be variations of adversarial training, and as far as I understand, only RS can provide probabilistic certified robust accuracy. Could you clarify this point?

As the reviewer response period is about to end and the authors have not addressed my questions, I have adjusted my score based on my current understanding of the paper. The paper has three main issues:

1. As a theoretically focused paper, its major problem lies in the lack of technical depth in the proofs, which makes me question whether the addressed problem is genuinely challenging and worth solving. As I pointed out in Questions 1-5, I have been trying to identify whether the theorems overcome some significant difficulties, such as relaxing key conditions or employing innovative mathematical tools. However, most of the computations appear to involve basic applications of probability theory.

2. The problem addressed in this paper does not seem particularly important. Certified robust accuracy, as a lower bound for empirical robust accuracy, theoretically means that any upper bound for empirical robust accuracy can also serve as an upper bound for certified accuracy. There are already many works on bounding empirical robust accuracy in adversarial PAC area. In other words, the paper focuses on a relatively small problem within certified robustness, which is not particularly compelling.

3. If the theoretical contributions are not strong, I would place greater emphasis on the experimental part of the paper. Unfortunately, the experiments also seem problematic. As I mentioned in Questions 6-9, the paper claims to propose an upper bound for probabilistic certified accuracy. However, the baselines compared seem to be adversarial training algorithms, and the specific implementation of randomized smoothing, the only method capable of providing certified robustness, is unclear. This makes it difficult for me to determine whether the claimed improvements represent a fair comparison. I recommend including more RS algorithms for comparison, such as the baselines discussed in [1].

Thus, I have adjusted my score and confidence level accordingly.

[1] Confidence-Aware Training of Smoothed Classifiers for Certified Robustness, Jeong et al., AAAI 2023.