mlsanityData to 7 Oct 2026

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

arXiv 2405.11547 ↗First posted 19 May 2024stat.ML cs.CR cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

37 of 66 references.

References · 37

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  4. 2015Domain-Adversarial Training of Neural Networkscited by 3,023
  5. 2016Adversarial examples in the physical worldcited by 1,762
  6. 2018Glow: Generative Flow with Invertible 1x1 Convolutionscited by 1,539
  7. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  8. 2016Adversarial Machine Learning at Scalecited by 934
  9. 2018Robustness May Be at Odds with Accuracycited by 873
  10. 2020Fast is better than free: Revisiting adversarial trainingcited by 723
  11. 2020On Adaptive Attacks to Adversarial Example Defensescited by 547
  12. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
25 more
  1. 2016Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samplescited by 439
  2. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  3. 2018Certified Defenses against Adversarial Examplescited by 305
  4. 2021Recent Advances in Adversarial Training for Adversarial Robustnesscited by 276
  5. 2019Human uncertainty makes classification more robustcited by 231
  6. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  7. 2018Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approachcited by 181
  8. 2022Robustness and Accuracy Could Be Reconcilable by (Proper) Definitioncited by 109
  9. 2021Orthogonalizing Convolutional Layers with the Cayley Transformcited by 105
  10. 2020Certified Defenses for Adversarial Patchescited by 100
  11. 2020SoK: Certified Robustness for Deep Neural Networkscited by 100
  12. 2019Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networkscited by 86
  13. 2019The Limitations of Adversarial Training and the Blind-Spot Attackcited by 63
  14. 2022Certified Training: Small Boxes are All You Needcited by 51
  15. 2021Fast Certified Robust Training with Short Warmupcited by 45
  16. 2022Is the Performance of My Deep Network Too Good to Be True? A Direct Approach to Estimating the Bayes Error in Binary Classificationcited by 24
  17. 2021Towards Evaluating and Training Verifiably Robust Neural Networkscited by 15
  18. 2021Evaluating State-of-the-Art Classification Models Against Bayes Optimalitycited by 15
  19. 2014Empirically Estimable Classification Bounds Based on a New Divergence Measurecited by 11
  20. 2019Learning to Benchmark: Determining Best Achievable Misclassification Error from Training Datacited by 10
  21. 2018Learning to Bound the Multi-class Bayes Errorcited by 9
  22. 2023Expressivity of ReLU-Networks under Convex Relaxationscited by 8
  23. 2021Evaluating Bayes Error Estimators on Real-World Datasets with FeeBeecited by 7
  24. 2022Accelerating Certified Robustness Training via Knowledge Transfercited by 7
  25. 2021The Fundamental Limits of Interval Arithmetic for Neural Networkscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 2.

7 papers.

  1. 2024How Does Bayes Error Limit Probabilistic Robust Accuracycited by 2
  2. 2025Universal Training of Neural Networks to Achieve Bayes Optimal Classification Accuracycited by 1
  3. 2025Correct-By-Construction: Certified Individual Fairness through Neural Network Trainingcited by 1
  4. 2026Rendering Data Unlearnable by Exploiting LLM Alignment Mechanismscited by 1
  5. 2025Get Global Guarantees: On the Probabilistic Nature of Perturbation Robustnesscited by 0
  6. 2025Towards Provably Unlearnable Examples via Bayes Error Optimisationcited by 0
  7. 2026Task-Relevant Representation Decoupling for Visual Reinforcement Learning Generalizationcited by 0