# Computability of Optimizers

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 62 references that are in the map.
- First posted on arXiv 15 Jan 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [DGM: A deep learning algorithm for solving partial differential equations](https://mlsanity.com/paper/1708.07469/) (2017)
- [The Modern Mathematics of Deep Learning](https://mlsanity.com/paper/2105.04026/) (2021)
- [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)
- [The troublesome kernel -- On hallucinations, no free lunches and the accuracy-stability trade-off in inverse problems](https://mlsanity.com/paper/2001.01258/) (2020)
- [How degenerate is the parametrization of neural networks with the ReLU activation function?](https://mlsanity.com/paper/1905.09803/) (2019)
- [Limitations of Deep Learning for Inverse Problems on Digital Hardware](https://mlsanity.com/paper/2202.13490/) (2022)

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

- [Bias Detection via Maximum Subgroup Discrepancy](https://mlsanity.com/paper/2502.02221/) (2025)
- [Reliable AI: Does the Next Generation Require Quantum Computing?](https://mlsanity.com/paper/2307.01301/) (2023)
- [Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization](https://mlsanity.com/paper/2408.06212/) (2024)
- [Optimisation Strategies for Ensuring Fairness in Machine Learning: With and Without Demographics](https://mlsanity.com/paper/2411.09056/) (2024)
- [humancompatible.detect: a Python Toolkit for Detecting Bias in AI Models](https://mlsanity.com/paper/2509.24340/) (2025)

## Abstract (arXiv)

Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.