<p>Generalised hardness of approximation (GHA) is the phenomenon that one can easily compute an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-approximation to a solution of a computational problem for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon> \epsilon _1 > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>></mo> <msub> <mi>ϵ</mi> <mn>1</mn> </msub> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, but for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\epsilon < \epsilon _1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo><</mo> <msub> <mi>ϵ</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> (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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Ω</mi> </math></EquationSource> </InlineEquation>, one can prove the existence of optimal NNs for solving the inverse problem for each <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {T}\in \Omega $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">T</mi> <mo>∈</mo> <mi mathvariant="normal">Ω</mi> </mrow> </math></EquationSource> </InlineEquation>, however, these optimal neural networks can only be computed to a certain accuracy <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\epsilon _1 > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϵ</mi> <mn>1</mn> </msub> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>. Below the approximation threshold <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\epsilon _1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ϵ</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$2\epsilon _1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msub> <mi>ϵ</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> 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.</p>

Generalised Hardness of Approximation and the SCI Hierarchy –On Determining the Boundaries of Training Algorithms in AI

期刊论文
出版模式：

开放获取
发表日期：

2026年7月30日

查看全文

Luca Eva Gazdag,
Alexander Bastounis,
Anders C. Hansen

摘要

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$ $ϵ > ϵ_{1} > 0$ , but for $\epsilon < \epsilon _1$ $ϵ < ϵ_{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 $ $T \in Ω$ , however, these optimal neural networks can only be computed to a certain accuracy $\epsilon _1 > 0$ $ϵ_{1} > 0$ . Below the approximation threshold $\epsilon _1$ $ϵ_{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\epsilon _1$ $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.