# Do stable neural networks exist for classification problems? -- A new view on stability in AI

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 82 references that are in the map.
- First posted on arXiv 15 Jan 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (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)
- [Rich feature hierarchies for accurate object detection and semantic segmentation](https://mlsanity.com/paper/1311.2524/) (2013)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (2018)
- [Audio Adversarial Examples: Targeted Attacks on Speech-to-Text](https://mlsanity.com/paper/1801.01944/) (2018)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Adversarial Robustness through Local Linearization](https://mlsanity.com/paper/1907.02610/) (2019)
- [Robust Large Margin Deep Neural Networks](https://mlsanity.com/paper/1605.08254/) (2016)
- [Deep Neural Network Approximation Theory](https://mlsanity.com/paper/1901.02220/) (2019)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [The gap between theory and practice in function approximation with deep neural networks](https://mlsanity.com/paper/2001.07523/) (2020)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Approximation spaces of deep neural networks](https://mlsanity.com/paper/1905.01208/) (2019)
- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [Nonlinear Approximation and (Deep) ReLU Networks](https://mlsanity.com/paper/1905.02199/) (2019)
- [The troublesome kernel -- On hallucinations, no free lunches and the accuracy-stability trade-off in inverse problems](https://mlsanity.com/paper/2001.01258/) (2020)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [Structure preserving deep learning](https://mlsanity.com/paper/2006.03364/) (2020)
- [Neural network approximation and estimation of classifiers with classification boundary in a Barron class](https://mlsanity.com/paper/2011.09363/) (2020)
- [The universal approximation theorem for complex-valued neural networks](https://mlsanity.com/paper/2012.03351/) (2020)

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

- [Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization](https://mlsanity.com/paper/2408.06212/) (2024)
- [The Price of Robustness: Stable Classifiers Need Overparameterization](https://mlsanity.com/paper/2603.02806/) (2026)

## Abstract (arXiv)

In deep learning (DL) the instability phenomenon is widespread and well documented, most commonly using the classical measure of stability, the Lipschitz constant. While a small Lipchitz constant is traditionally viewed as guarantying stability, it does not capture the instability phenomenon in DL for classification well. The reason is that a classification function -- which is the target function to be approximated -- is necessarily discontinuous, thus having an 'infinite' Lipchitz constant. As a result, the classical approach will deem every classification function unstable, yet basic classification functions a la 'is there a cat in the image?' will typically be locally very 'flat' -- and thus locally stable -- except at the decision boundary. The lack of an appropriate measure of stability hinders a rigorous theory for stability in DL, and consequently, there are no proper approximation theoretic results that can guarantee the existence of stable networks for classification functions. In this paper we introduce a novel stability measure mathscrS(f), for any classification function f, appropriate to study the stability of discontinuous functions and their approximations. We further prove two approximation theorems: First, for any ε > 0 and any classification function f on a compact set, there is a neural network (NN) psi, such that psi - f neq 0 only on a set of measure < ε, moreover, mathscrS(psi) ≥ mathscrS(f) - ε (as accurate and stable as f up to ε). Second, for any classification function f and ε > 0, there exists a NN psi such that psi = f on the set of points that are at least ε away from the decision boundary.