1
$\begingroup$

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
$\endgroup$

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.