Theory of Computing
-------------------
Title     : Training Fully Connected Neural Networks is ∃ℝ-Complete
Authors   : Daniel Bertschinger, Christopher Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber
Volume    : 22
Number    : 6
Pages     : 1-48
URL       : https://theoryofcomputing.org/articles/v022a006

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 ER-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'21). A consequence of this is that a combinatorial
search algorithm like the one by Arora, Basu, Mianjy, and Mukherjee
(ICLR'18) is impossible for networks with more than one output
dimension, unless  NP = ER.


---------------


An extended abstract of this paper appeared in the proceedings of
"Advances in Neural Information Processing Systems 36" (NeurIPS 2023).