# Generalised hardness of approximation and the SCI hierarchy -- On determining the boundaries of training algorithms in AI

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2022.

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

- [On the consistent reasoning paradox of intelligence and optimal trust in AI: The power of 'I don't know'](https://mlsanity.com/paper/2408.02357/) (2024)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation](https://mlsanity.com/paper/2312.11425/) (2023)
- [Do stable neural networks exist for classification problems? -- A new view on stability in AI](https://mlsanity.com/paper/2401.07874/) (2024)
- [Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization](https://mlsanity.com/paper/2408.06212/) (2024)

## Abstract (arXiv)

Generalised hardness of approximation (GHA) is the phenomenon that one can easily compute an ε-approximation to a solution of a computational problem for ε > ε1 > 0, but for ε < ε1 (the approximation threshold) it suddenly becomes hard, for example, non-computable or intractable (non-polynomial time). In this paper we demonstrate the phenomenon that GHA happens when using AI techniques for solving inverse problems, namely training neural networks (NNs) to optimally perform on the training data. In particular, for any non-zero underdetermined linear inverse problem the following phase transition can occur: For a certain family of training sets Omega, one can prove the existence of optimal NNs for solving the inverse problem for each T ∈ Omega, however, these optimal neural networks can only be computed to a certain accuracy ε1 > 0. Below the approximation threshold ε1, not only does it become intractable to compute the NNs, it becomes impossible regardless of computing power, and no randomised algorithm can solve the problem with probability better than 1/2. Moreover, despite the existence of a stable optimal NN, any attempts of computing it below two times the approximation threshold 2ε1 will yield an unstable NN. Our results use and extend the current mathematical framework of the Solvability Complexity Index (SCI) hierarchy and initiate a program for analysing the GHA phenomenon throughout computational mathematics and AI. GHA generalises the phenomenon of hardness of approximation in discrete computations to arbitrary computational problems.