# How Does Bayes Error Limit Probabilistic Robust Accuracy

arXiv: https://arxiv.org/abs/2405.14923 · HTML: https://mlsanity.com/paper/2405.14923/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 54 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 30 of 34)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality](https://mlsanity.com/paper/1801.02613/) (2018)
- [Human uncertainty makes classification more robust](https://mlsanity.com/paper/1908.07086/) (2019)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [The Limitations of Adversarial Training and the Blind-Spot Attack](https://mlsanity.com/paper/1901.04684/) (2019)
- [Certified Training: Small Boxes are All You Need](https://mlsanity.com/paper/2210.04871/) (2022)
- [Fast Certified Robust Training with Short Warmup](https://mlsanity.com/paper/2103.17268/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [RobOT: Robustness-Oriented Testing for Deep Learning Systems](https://mlsanity.com/paper/2102.05913/) (2021)
- [Is the Performance of My Deep Network Too Good to Be True? A Direct Approach to Estimating the Bayes Error in Binary Classification](https://mlsanity.com/paper/2202.00395/) (2022)
- [PRoA: A Probabilistic Robustness Assessment against Functional Perturbations](https://mlsanity.com/paper/2207.02036/) (2022)
- [Evaluating State-of-the-Art Classification Models Against Bayes Optimality](https://mlsanity.com/paper/2106.03357/) (2021)
- [Empirically Estimable Classification Bounds Based on a New Divergence Measure](https://mlsanity.com/paper/1412.6534/) (2014)
- [Maximum a Posteriori Estimators as a Limit of Bayes Estimators](https://mlsanity.com/paper/1611.05917/) (2016)
- [Towards Practical Robustness Analysis for DNNs based on PAC-Model Learning](https://mlsanity.com/paper/2101.10102/) (2021)
- [Generalized Bhattacharyya and Chernoff upper bounds on Bayes error using quasi-arithmetic means](https://mlsanity.com/paper/1401.4788/) (2014)
- [Learning to Benchmark: Determining Best Achievable Misclassification Error from Training Data](https://mlsanity.com/paper/1909.07192/) (2019)
- [Learning to Bound the Multi-class Bayes Error](https://mlsanity.com/paper/1811.06419/) (2018)

## Built on by (most cited first, 2 of 2)

- [Get Global Guarantees: On the Probabilistic Nature of Perturbation Robustness](https://mlsanity.com/paper/2508.19183/) (2025)
- [Towards Provably Unlearnable Examples via Bayes Error Optimisation](https://mlsanity.com/paper/2511.08191/) (2025)

## Abstract (arXiv)

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