Complexity of Neural Network Training and ETR: Extensions with
  Effectively Continuous Functions
Teemu Hankala Miika Hannula Juha Kontinen Jonni Virtema
We study the complexity of the problem of training neural networks defined
via various activation functions. The training problem is known to be
existsR-complete with respect to linear activation functions and the ReLU
activation function. We consider the complexity of the problem with respect to
the sigmoid activation function and other effectively continuous functions. We
show that these training problems are polynomial-time many-one bireducible to
the existential theory of the reals extended with the corresponding activation
functions. In particular, we establish that the sigmoid activation function
leads to the existential theory of the reals with the exponential function. It
is thus open, and equivalent with the decidability of the existential theory of
the reals with the exponential function, whether training neural networks using
the sigmoid activation function is algorithmically solvable. In contrast, we
obtain that the training problem is undecidable if sinusoidal activation
functions are considered. Finally, we obtain general upper bounds for the
complexity of the training problem in the form of low levels of the
arithmetical hierarchy.