Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete

arXiv:2204.01368v3 Announce Type: replace-cross
Abstract: 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 …

abstract arxiv biases cs.cc cs.lg cs.ne data decision layer network networks neural network neural networks polynomial set training type weights and biases