2024
Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions
AAAI 2024technical
The training problem of neural networks (NNs) is known to be ER-complete with respect to ReLU and linear activation functions. We show that the training problem for NNs equipped with arbitrary activation functions is polynomial-time bireducible to the existential theory of the reals extended with th…