# Certified Robust Accuracy of Neural Networks Are Bounded due to Bayes Errors

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 66 references that are in the map.
- First posted on arXiv 19 May 2024.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [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)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Recent Advances in Adversarial Training for Adversarial Robustness](https://mlsanity.com/paper/2102.01356/) (2021)
- [Human uncertainty makes classification more robust](https://mlsanity.com/paper/1908.07086/) (2019)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Robustness and Accuracy Could Be Reconcilable by (Proper) Definition](https://mlsanity.com/paper/2202.10103/) (2022)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks](https://mlsanity.com/paper/1911.00937/) (2019)
- [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)
- [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)
- [Evaluating State-of-the-Art Classification Models Against Bayes Optimality](https://mlsanity.com/paper/2106.03357/) (2021)
- [Towards Evaluating and Training Verifiably Robust Neural Networks](https://mlsanity.com/paper/2104.00447/) (2021)

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

- [How Does Bayes Error Limit Probabilistic Robust Accuracy](https://mlsanity.com/paper/2405.14923/) (2024)
- [BOLT: Universal Classifier Training via a Bayes-Error Upper Bound](https://mlsanity.com/paper/2501.07754/) (2025)
- [Correct-By-Construction: Certified Individual Fairness through Neural Network Training](https://mlsanity.com/paper/2508.15642/) (2025)
- [Rendering Data Unlearnable by Exploiting LLM Alignment Mechanisms](https://mlsanity.com/paper/2601.03401/) (2026)
- [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)
- [Task-Relevant Representation Decoupling for Visual Reinforcement Learning Generalization](https://mlsanity.com/paper/2607.00796/) (2026)

## Abstract (arXiv)

Adversarial examples pose a security threat to many critical systems built on neural networks. While certified training improves robustness, it also decreases accuracy noticeably. Despite various proposals for addressing this issue, the significant accuracy drop remains. More importantly, it is not clear whether there is a certain fundamental limit on achieving robustness whilst maintaining accuracy. In this work, we offer a novel perspective based on Bayes errors. By adopting Bayes error to robustness analysis, we investigate the limit of certified robust accuracy, taking into account data distribution uncertainties. We first show that the accuracy inevitably decreases in the pursuit of robustness due to changed Bayes error in the altered data distribution. Subsequently, we establish an upper bound for certified robust accuracy, considering the distribution of individual classes and their boundaries. Our theoretical results are empirically evaluated on real-world datasets and are shown to be consistent with the limited success of existing certified training results, e.g., for CIFAR10, our analysis results in an upper bound (of certified robust accuracy) of 67.49%, meanwhile existing approaches are only able to increase it from 53.89% in 2017 to 62.84% in 2023.