Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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.
There are a few technical papers and books on the topic
Computational Limitations on Learning from Examples (1988) by Leonard Pitt and Leslie G. Valiant, published in Journal of the ACM
Training a 3-node neural network is NP-complete (1992) by Avrim L. Blum and Ronald L. Rivest, published in Neural Networks
Computational complexity of neural networks: a survey (1994) by Pekka Orponen, published in Nordic Journal of Computing
On the relative time complexities of standard and conjugate gradient backpropagation (1994) by J. V. Stone and R. Lister, published in IEEE
Neural Networks - A Systematic Introduction (1996), specifically chapter 10 The Complexity of Learning, a book by Raul Rojas
Complexity Analysis of Multilayer Perceptron Neural Network Embedded into a Wireless Sensor Network (2014) by Gursel Serpen and Zhenning Gao, published in Complex Adaptive Systems
On the Computational Efficiency of Training Neural Networks (2014) by Roi Livni, Shai Shalev-Shwartz and Ohad Shamir, published in NIPS 2014
Convolutional Neural Networks at Constrained Time Cost (2014) Kaiming He and Jian Sun, published in IEEE Conference on Computer Vision and Pattern Recognition (2015)
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2018) by Surbhi Goel and Adam Klivans
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.
