Are Probabilistic Robust Accuracy Bounded
bayes error;Probabilistic Robustness
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
- 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?
- 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.
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.
- I do not see any major weakness in the paper. Although, I do have a few questions regarding the experimental setup.
Yes
No ethics review needed.
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?
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.
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.
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).
A theorectical upper bound of probabilistic robust accuracy is presented.
@inproceedings{
anonymous2024are,
title={Are Probabilistic Robust Accuracy Bounded},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=fVgUXaesSS},
note={under review}
}
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 whether an upper limit on accuracy exists 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
bayes error Probabilistic Robustness
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/df87a02523496565fe82e4bb9459fddcac92d12e.pdf
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Are Probabilistic Robust Accuracy Bounded
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission