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:
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.
