  Adversarial examples pose a security threat to many critical systems built on
neural networks. Given that deterministic robustness often comes with
significantly reduced accuracy, probabilistic robustness (i.e., the probability
of having the same label with a vicinity is $\ge 1-\kappa$) has been proposed
as a promising way of achieving robustness whilst maintaining accuracy.
However, existing training methods for probabilistic robustness still
experience non-trivial accuracy loss. It is unclear whether there is an upper
bound on the accuracy when optimising towards probabilistic robustness, and
whether there is a certain relationship between $\kappa$ and this 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 prove that with optimal probabilistic robustness,
each probabilistically robust input is also deterministically robust in a
smaller vicinity. We also 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.
