论文标题
培训完全连接的神经网络是$ \存在\ mathbb {r} $ - 完成
Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
论文作者
论文摘要
我们考虑了为两层完全连接的神经网络寻找权重和偏见的问题，以尽可能拟合一组给定的数据点，也称为“经验思路mminimation”。我们的主要结果是，关联的决策问题是$ \存在\ mathbb {r} $ - 完整，即多项式时间等同于确定与整数系数是否具有任何真正根源的多元多项式。此外，我们证明，即使所有数据点都是合理的，也需要任意较大程度的代数数量，以便能够将某些实例训练为最佳。我们的结果已经适用于具有两个输入，两个输出和一个隐藏层神经元的完全连接的实例。因此，我们加强了亚伯拉罕森，克莱斯特和米尔特佐夫的结果[Neurips 2021]。结果是，与Arora，Basu，Mianjy和Mukherjee的组合搜索算法一样，对于具有多个输出维度的网络而言，不可能是不可能的，除非$ \ MATHSF {np} = \ exists = \ exists \ Mathbb {r} $。
We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalRiskMinimization. Our main result is that the associated decision problem is $\exists\mathbb{R}$-complete, that is, polynomial-time equivalent to determining whether a multivariate polynomial with integer coefficients has any real roots. Furthermore, we prove that algebraic numbers of arbitrarily large degree are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless $\mathsf{NP}=\exists\mathbb{R}$.
