In the paper "Provable bounds for learning some deep representations", an autoencoder like a model is constructed with discrete weights and several results are proven using some random-graph theory, but I never saw any papers similar to this. i.e bounds on neural networks using random graph assumptions.

What are some resources (e.g. books or papers) regarding the time and space complexity of training neural networks?

I'm particularly interested in convolutional neural networks.


1 Answer 1


There are a few technical papers and books on the topic

However, note that gradient descent (and other optimization algorithms) and the back-propagation algorithm are numerical algorithms (that is, they deal with numerical errors), so the time complexity is not the only factor affecting the actual performance of these algorithms and models.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .