It is often stated that training a neural network is "well-known" to be NP-hard. Looking through the literature the often quoted papers are 1 and [2].
[1] proves the NP-hardness for finding an exact match, i.e. finding a hypothesis $h$ with $\forall i\in I: h(x_i)=y_i$ for step-function type neural networks. [2] further proves for that type of network even finding the best approximate solution, i.e. minimizing $\#\{i \in I:h(x_i)\not=y_i \}$ is NP-hard.
However that does not immediately generalize to other activation functions, does it? I have found [3] which seems to prove the same for ReLu, though I do not have access to the paper right now.
My question therefore is: Is there any literature that proves the NP-hardness of finding the best approximate solution of a one-hidden-layer neural network for all activation functions (that are not polynomials)?
$\\$
- Training a 3-Node Neural Network is NP-Complete - Avrim L. Blum and Ronald L. Rivest
- Hardness results for neural networkapproximation problems - Peter L. Bartletta, Shai Ben-David
- Complexity of training ReLU neural network - Digvijay Boob, Santanu S. Dey, Guanghui Lan
