# Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 39 of its 93 references that are in the map.
- First posted on arXiv 12 Aug 2024.

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Taming Transformers for High-Resolution Image Synthesis](https://mlsanity.com/paper/2012.09841/) (2020)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [A Survey of Human-in-the-loop for Machine Learning](https://mlsanity.com/paper/2108.00941/) (2021)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Quantization Networks](https://mlsanity.com/paper/1911.09464/) (2019)
- [Explaining Image Classifiers by Counterfactual Generation](https://mlsanity.com/paper/1807.08024/) (2018)
- [Explainable Deep Learning: A Field Guide for the Uninitiated](https://mlsanity.com/paper/2004.14545/) (2020)
- [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)
- [The Modern Mathematics of Deep Learning](https://mlsanity.com/paper/2105.04026/) (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)
- [Can AI Assistants Know What They Don't Know?](https://mlsanity.com/paper/2401.13275/) (2024)
- [Computing Systems for Autonomous Driving: State-of-the-Art and Challenges](https://mlsanity.com/paper/2009.14349/) (2020)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [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)
- [The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learning](https://mlsanity.com/paper/2110.15734/) (2021)
- [Recent Advances in Deep Learning: An Overview](https://mlsanity.com/paper/1807.08169/) (2018)
- [Limitations of Deep Learning for Inverse Problems on Digital Hardware](https://mlsanity.com/paper/2202.13490/) (2022)
- [A simple approach for quantizing neural networks](https://mlsanity.com/paper/2209.03487/) (2022)
- [Explaining Image Classifiers with Multiscale Directional Image Representation](https://mlsanity.com/paper/2211.12857/) (2022)

## Abstract (arXiv)

The unwavering success of deep learning in the past decade led to the increasing prevalence of deep learning methods in various application fields. However, the downsides of deep learning, most prominently its lack of trustworthiness, may not be compatible with safety-critical or high-responsibility applications requiring stricter performance guarantees. Recently, several instances of deep learning applications have been shown to be subject to theoretical limitations of computability, undermining the feasibility of performance guarantees when employed on real-world computers. We extend the findings by studying computability in the deep learning framework from two perspectives: From an application viewpoint in the context of classification problems and a general limitation viewpoint in the context of training neural networks. In particular, we show restrictions on the algorithmic solvability of classification problems that also render the algorithmic detection of failure in computations in a general setting infeasible. Subsequently, we prove algorithmic limitations in training deep neural networks even in cases where the underlying problem is well-behaved. Finally, we end with a positive observation, showing that in quantized versions of classification and deep network training, computability restrictions do not arise or can be overcome to a certain degree.