# The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 16 references that are in the map.
- First posted on arXiv 13 Sep 2023.

## Builds on (most cited first, 11 of 11)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [The mathematics of adversarial attacks in AI -- Why deep learning is unstable despite the existence of stable neural networks](https://mlsanity.com/paper/2109.06098/) (2021)
- [On Adversarial Examples and Stealth Attacks in Artificial Intelligence Systems](https://mlsanity.com/paper/2004.04479/) (2020)
- [The Feasibility and Inevitability of Stealth Attacks](https://mlsanity.com/paper/2106.13997/) (2021)
- [High-dimensional separability for one- and few-shot learning](https://mlsanity.com/paper/2106.15416/) (2021)
- [Stochastic Separation Theorems](https://mlsanity.com/paper/1703.01203/) (2017)
- [Rosenblatt's first theorem and frugality of deep learning](https://mlsanity.com/paper/2208.13778/) (2022)

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

- [Weakly Supervised Learners for Correction of AI Errors with Provable Performance Guarantees](https://mlsanity.com/paper/2402.00899/) (2024)
- [Simplicity within biological complexity](https://mlsanity.com/paper/2405.09595/) (2024)
- [Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization](https://mlsanity.com/paper/2408.06212/) (2024)
- [Networks with Finite VC Dimension: Pro and Contra](https://mlsanity.com/paper/2502.02679/) (2025)
- [Theoretical Lower Bounds on the Robustness of Deep ReLU Networks](https://mlsanity.com/paper/2602.18674/) (2026)

## Abstract (arXiv)

In this work, we assess the theoretical limitations of determining guaranteed stability and accuracy of neural networks in classification tasks. We consider classical distribution-agnostic framework and algorithms minimising empirical risks and potentially subjected to some weights regularisation. We show that there is a large family of tasks for which computing and verifying ideal stable and accurate neural networks in the above settings is extremely challenging, if at all possible, even when such ideal solutions exist within the given class of neural architectures.