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)?


  1. Training a 3-Node Neural Network is NP-Complete - Avrim L. Blum and Ronald L. Rivest
  2. Hardness results for neural networkapproximation problems - Peter L. Bartletta, Shai Ben-David
  3. Complexity of training ReLU neural network - Digvijay Boob, Santanu S. Dey, Guanghui Lan

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.