1
$\begingroup$

I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

  1. How is training complexity related to network topology ?
  2. How is training complexity related to the complexity of the decision boundary?
$\endgroup$
1
$\begingroup$

At present the theory of computational complexity has little useful to say. This is largely an empirical science: to find out how many epochs of training are needed or is optimal, the only way to know for sure is to try it and see. While there is some limited amount of theory, the theory isn't very useful in practice. Ultimately, we don't really understand why deep learning works or how well it works or exactly what conditions are needed for it to work.

Training usually involves a series of epochs. The time for each epoch is proportional to the time to evaluate the network on each of the training set instances, once. There's no theory about the number of epochs needed. However, in many situations the number of epochs is a relatively small number, say, 20-100 -- not always, but fairly often. So, that gives you some idea.

Ultimately, topology doesn't seem to affect training time much except insofar as it affects the time to evaluate the classifier on an instance. It could influence the number of epochs too, but on many networks seen in practice, it doesn't seem to have a large influence for many of the architectures we use in practice. However, this could be a consequence of the fact that we typically select architectures that do perform well with a reasonable amount of training (i.e., the architecture is often selected so a huge number of epochs isn't needed). In any case, this isn't a hard-and-fast rule.

Bottom line: ultimately, we understand very little about the complexity of neural networks, the complexity of training, or rigorous/well-founded/provable answers to your questions.

$\endgroup$
  • $\begingroup$ I recall from a long time ago (sometime in 2007) a text book stating very briefly that training a feed-forward perceptron was NP-complete. I assumed that some progress would have been made in the interim. $\endgroup$ – Sasha the Noob Dec 19 '17 at 2:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.