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

Understand

Generalised hardness of approximation (GHA) is the phenomenon that one can easily compute an $\epsilon$-approximation to a solution of a computational problem for $\epsilon > \epsilon_1 > 0$, but for $\epsilon < \epsilon_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 $\mathcal{T} \in \Omega$, however, these optimal neural networks can only be computed to a certain accuracy $\epsilon_1 > 0$.
• Below the approximation threshold $\epsilon_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.