Are Probabilistic Robust Accuracy Bounded

Authors: Ruihan Zhang, Jun Sun
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: bayes error, Probabilistic Robustness

Abstract:
Adversarial samples pose a security threat to many critical systems built on neural networks. It has recently been proven that achieving deterministic robustness (*i.e.*, complete elimination of adversarial samples) always comes at an unbearable cost to accuracy. As a result, probabilistic robustness (where the probability of retaining the same label within a vicinity is at least $1 - \kappa$) has been proposed as a promising compromise. However, existing training methods for probabilistic robustness still experience non-trivial accuracy loss. It remains an open question what the upper limit on accuracy is when optimizing for probabilistic robustness, and whether there is a specific relationship between $\kappa$ and this potential bound. This work studies these problems from a Bayes error perspective. We find that while Bayes uncertainty does affect probabilistic robustness, its impact is smaller than that on deterministic robustness. This reduced Bayes uncertainty allows a higher upper bound on probabilistic robust accuracy than that on deterministic robust accuracy. Further, we show that voting within the vicinity always improves probabilistic robust accuracy and the upper bound of probabilistic robust accuracy monotonically increases as $\kappa$ grows. Our empirical findings also align with our results. This study thus presents a theoretical argument supporting probabilistic robustness as the appropriate target for achieving neural network robustness.

Decision: reject
Reviewer scores: 3, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730674335068

thread_type:
official_review

<thread_object>
creator: reviewer_evqe

<content>
summary:
The paper studies probabilistic robust classifiers (PRC) as defined in Robey et al. (2022). It derives an expression of the Bayes error that bounds the PRC. They further, show that this bound is bounded between the Bayes error of the vanilla classifier and the deterministically robust Bayes error. They evaluate the PRC accuracies and Bayes errors empirically.

strengths:
S1: The paper is well structured and actively helps the user to get through it. It often announces next steps and summarizes theorems and key insights in plain language. That helps tremendously in parsing the paper. E.g. L203-L207

S2: The paper is a natural extension of previous work to probabilistic robust classifiers. Understanding their properties is an important endeavor. The result does not come as a surprise ("accuracy vs robustness guarantee" trade-off is well established), but it is original work and a worthwhile contribution to the robust ML community, furthering our understanding of these models.

S3: The authors provide the code for their experiments.

weaknesses:
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 dont 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 $<< 0.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 \rightarrow 0$?
I would suggest the authors include more $\kappa$ values in this work and more datasets / architectures in a revision or future works section.

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.

W3: The work would benefit from a thorough proof-reading. For example (not complete list):

- The title is grammatically incorrect. Should probably be: "Probabilistic robust accuracy is bounded".
- Comma after "classses" incorrect (L178), "statistiCAL significance" (L425)
- The language throughout the paper could be more nuanced. For instance, "The fundamental problem in this study" (L194) is not clear. It is the "problem studied in this work", not the "problem of the work". "unbearable" in the abstract is too colloquial.
- L224 should be $\mu_k(x) \triangleq$ ...
- "whereas" in line 536 is the wrong word.
I suggest the authors proofread the paper carefully. 

**Minor**

MW1: The subscripts for the errors in Section 3.1 are only explained long after introducing them (L251 to be precise). Moving up that section and explaining subscripts before presenting them can save the reader some time wondering what $e_{cor}$ in Eq 9 and $e_{cns}$ ins Eq 11 are.

MW2: The authors don't "compute" the voting classifier, they estimate it L(428-L429).

questions:
Q1: The voting classifier comes out of nowhere in L428. What is the rationale behind presenting it there?

Q2: What are the parameters for cohen RS? Number of samples etc, threshold for abstaining etc. (L453)

Q3: The authors seem surprised that the accuracy is bounded below the Bayes error, i.e. the authors state "It remains an open question whether an upper limit on accuracy exists when optimizing for probabilistic robustness" (L015-L017). To me it seems trivial that a Bayes classifier exists and that it bounds the accuracy of any other the classifier (very much by the definition of the Bayes classifier). I value the contribution of deriving _what_ it is, but I struggle to understand why it was debatable _whether_ it exists. Could the authors please clarify this point?

Q4: "Deterministic robustness requires a zero probability of adversarial samples..." (L135). This is necessary but not sufficient for determinsitic robustness, in my opinion. If there exists an adversary in the neigbourhood of $x$ with measure 0, the classifier is not deterministically robust.

Q5: Why are 50% of adversarial samples in the vicinity considered acceptable for Cohen et al. (2019)? (see L144). The authors list Gaussian Smoothing under "probabilistic" robustness. In my opinion, this is incorrect. The classifier itself is _deterministically robust_ and the probabilistic nature comes in as we need to approximate the true classifier, not from the classiifer itself. Is there any literature that proves that e.g. Eq 5 holds for the empirical approximation to the smoothed classifier for some reasonable $\mathcal{V}(x)$?

Q: Figure 2 and 3 contains estimates of the Bayes errors to bound the accuracies above. How precise is this estimate? Is it computationally tractable to compute this on CIFAR-100, TinyImageNet or similar datasets?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721411848

thread_type:
official_review

<thread_object>
creator: reviewer_1vxa

<content>
summary:
This paper investigates the theoretical limits of probabilistic robust accuracy for neural networks in the face of adversarial attacks, using a Bayes error framework. The authors investigate whether probabilistic robustness can achieve a higher upper bound on robust accuracy than deterministic robustness, given the Bayes error, which represents the irreducible error inherent in classification tasks. The paper's findings are validated empirically across multiple datasets, demonstrating that probabilistic robustness is a better option in comparison to deterministic robustness.

strengths:
- The paper presents a novel contribution by rigorously analyzing the upper bound of probabilistic robust accuracy from a Bayes error perspective. 
- The work provides a rigorous theoretical analysis and the way the paper is written makes the mathematics easy to follow.
- The theoretical analysis and claims are properly supported by the experiments in the paper.

weaknesses:
- I do not see any major weakness in the paper. Although, I do have a few questions regarding the experimental setup.

questions:
- 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?

- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731007502486

thread_type:
official_review

<thread_object>
creator: reviewer_mx9g

<content>
summary:
The submission studies the Bayes error of probabilistic robustness. The notion is that robustness is confirmed if the wrong prediction probability is smaller than some threshold. The submission theoretically analyzed the Bayes error under this notion, derived a necessary condition for the Bayes optimal classifier, and revealed its relation with deterministic robust accuracy and the upper bound of vanilla accuracy. Empirical results show that voting increases probabilistic robust accuracy.

strengths:
1. Comprehensive and novel theoretical analysis of probabilistic robustness notion from the Beyes error perspective. The analysis reveals that the Bayes-optimal classifier has the voting property (Theorem 3.2), which is of practical value and systematically connects probabilistic robustness with deterministic robustness and vanilla accuracy.

2. The presentation is good. Content is well organized and easy to follow.

weaknesses:
1. The analysis largely inherits the notion and methodology from [Zhang and Sun, CAV 2024]. Technical novelty is not very significant.

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



Minor:
1. Line 350: vicninty -> vicinity
2. Figure 2: what do $b_a, b_p, b_d$ mean? Some explanation preferred.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731133749189

thread_type:
official_review

<thread_object>
creator: reviewer_8ryv

<content>
summary:
The paper investigates probabilistic robustness in neural networks, proposing it as a feasible alternative to deterministic robustness against adversarial samples. Using Bayes error as a foundation, the study demonstrates that probabilistic robust accuracy can achieve a higher bound than deterministic robust accuracy due to reduced uncertainty. Theoretical results reveal that the accuracy bound for probabilistic robustness improves as κ increases, validated empirically through experiments on various datasets.

strengths:
1. The paper is well-structured, with a clear and logical flow throughout.
2. The mathematical derivations are thorough, and the background definitions are comprehensive, making it easier for readers to grasp the problem the authors aim to address.

weaknesses:
1. 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.

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

questions:
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 impractica? If so, does this mean that the derived bound serves primarily as an analytical perspective on robustness rather than offering practical experimental guidance?

---

**Post-Rebuttal Comments**  

Since I can no longer provide further comments at this stage, I am submitting my final response here.  

After reading the rebuttal, I think Issue 1 still remains. The authors have not explicitly identified the technical challenges addressed in their proofs, and I still find the proofs insufficiently solid.  

Regarding Issue 2, I would first like to clarify that PAC bounds are also model-agnostic and hold uniformly for classifiers within the hypothesis class. Additionally, the authors did not address my Questions 6-7. In my view, the method used by the authors to estimate the Bayes error is the same as that of Ishida et al., 2023, and the paper does not propose its own estimation method tailored to the task of certified robustness.  

For Issue 3, the authors misunderstood my question. The bounds provided in this paper are for probabilistic certified robust accuracy, while the current methods capable of providing probabilistic certified accuracy are those based on randomized smoothing (noting that this involves adding Gaussian noise during prediction, not just at training time). The baselines compared in the paper do not provide certified robust accuracy during prediction, so I find the experiments problematic. Moreover, the idea of voting (Table 1) is precisely the concept used in randomized smoothing, where Gaussian noise is added during prediction for voting.  

For these reasons, I maintain my score.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates the probabilistic robustness with focus on deriving an upper bound of probabilistic robust accuracy through bayes error. The finding and derivation on the monotonic relation between probabilistic accuracy upper bound and tolerance level is interesting but not surprising. There are some discussions in the rebuttal regarding the theoretical and experimental results, topic of interest, and significance of the results. In my opinion, this topic is of interest to the robust ML community, however the current form of the paper is not qualified yet for publications, with a few major recommendations to further strengthen the paper: (1) overcomplicated presentation of the main results in Sec 3, the authors are suggested to present the most important results and make the structure easy to follow. Current form contains too many branches and requires reorganization. (2) missing connection to probabilistic robustness literature and baselines, specifically the probabilistic certified robustness / verification in the neural network literature. (3) experiment result: randomized smoothing belongs to deterministic robustness instead of probabilistic robustness, the incorporation of RS in the experiments is questionable and confusing. The authors are also encouraged to take into account the reviewers suggestions/confusions in the rebuttal period to further improve the clarity and strength the results of the paper.