Answers.Body: <p>There are a few technical papers and books on the topic</p>
  
  <ul>
  <li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.6387&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Computational Limitations on Learning from Examples</a> (1988) by Leonard Pitt and Leslie G. Valiant, published in Journal of the ACM</p></li>
  <li><p><a href="https://www.sciencedirect.com/science/article/pii/S0893608005800103" rel="nofollow noreferrer">Training a 3-node neural network is NP-complete</a> (1992) by Avrim L. Blum and Ronald L. Rivest, published in Neural Networks</p></li>
  <li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.7434&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Computational complexity of neural networks: a survey</a> (1994) by Pekka Orponen, published in Nordic Journal of Computing</p></li>
  <li><p><a href="https://ieeexplore.ieee.org/document/374143" rel="nofollow noreferrer">On the relative time complexities of standard and conjugate gradient backpropagation</a> (1994) by J. V. Stone and R. Lister, published in IEEE</p></li>
  <li><p><a href="https://page.mi.fu-berlin.de/rojas/neural/" rel="nofollow noreferrer">Neural Networks - A Systematic Introduction</a> (1996), specifically chapter 10 <a href="https://page.mi.fu-berlin.de/rojas/neural/chapter/K10.pdf" rel="nofollow noreferrer">The Complexity of Learning</a>, a book by Raul Rojas</p></li>
  <li><p><a href="https://core.ac.uk/download/pdf/82200790.pdf" rel="nofollow noreferrer">Complexity Analysis of Multilayer Perceptron Neural Network Embedded into a Wireless Sensor Network</a> (2014) by Gursel Serpen and Zhenning Gao, published in Complex Adaptive Systems</p></li>
  <li><p><a href="https://papers.nips.cc/paper/5267-on-the-computational-efficiency-of-training-neural-networks.pdf" rel="nofollow noreferrer">On the Computational Efficiency of Training Neural Networks</a> (2014) by Roi Livni, Shai Shalev-Shwartz and Ohad Shamir, published in NIPS 2014</p></li>
  <li><p><a href="https://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/He_Convolutional_Neural_Networks_2015_CVPR_paper.pdf" rel="nofollow noreferrer">Convolutional Neural Networks at Constrained Time Cost</a> (2014) Kaiming He and  Jian Sun, published in IEEE Conference on Computer Vision and Pattern Recognition (2015)</p></li>
  <li><p><a href="https://arxiv.org/pdf/1709.06010.pdf" rel="nofollow noreferrer">Learning Neural Networks with Two Nonlinear Layers in Polynomial Time</a> (2018) by Surbhi Goel and Adam Klivans</p></li>
  </ul>
  
  <p>However, note that gradient descent (and other optimization algorithms) and the <a href="http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Fall.2016/pdfs/Werbos.backprop.pdf" rel="nofollow noreferrer">back-propagation algorithm</a> are <a href="https://en.wikipedia.org/wiki/Numerical_analysis" rel="nofollow noreferrer">numerical algorithms</a> (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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T23:26:07.133Z
Answers.LastActivityDate: 2019-06-27T23:35:14.717Z
Answers.LastEditDate: 2019-06-27T23:35:14.717Z
Answers.UserDisplayName: nbro
Body: <p>In the paper "<a href="https://arxiv.org/abs/1310.6343" rel="nofollow noreferrer">Provable bounds for learning some deep representations</a>", 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. </p>
  
  <p><em>What are some resources (e.g. books or papers) regarding the time and space complexity of training neural networks?</em></p>
  
  <p>I'm particularly interested in convolutional neural networks.</p>
  
Tags: <convolutional-neural-networks><reference-request><time-complexity><complexity-theory>
Title: What are some resources regarding the complexity of training neural networks?
UserDisplayName: thecomplexitytheorist
ThreadText: # What are some resources regarding the complexity of training neural networks?
  
  (Asked by: username_0 on 2018-07-02)
  
  In the paper "[Provable bounds for learning some deep representations](https://arxiv.org/abs/1310.6343)", 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.
  
  **Tags:** convolutional-neural-networks, reference-request, time-complexity, complexity-theory
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-27. Score: 1
  
  There are a few technical papers and books on the topic
  
  * [Computational Limitations on Learning from Examples](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.6387&rep=rep1&type=pdf) (1988) by Leonard Pitt and Leslie G. Valiant, published in Journal of the ACM
  * [Training a 3-node neural network is NP-complete](https://www.sciencedirect.com/science/article/pii/S0893608005800103) (1992) by Avrim L. Blum and Ronald L. Rivest, published in Neural Networks
  * [Computational complexity of neural networks: a survey](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.7434&rep=rep1&type=pdf) (1994) by Pekka Orponen, published in Nordic Journal of Computing
  * [On the relative time complexities of standard and conjugate gradient backpropagation](https://ieeexplore.ieee.org/document/374143) (1994) by J. V. Stone and R. Lister, published in IEEE
  * [Neural Networks - A Systematic Introduction](https://page.mi.fu-berlin.de/rojas/neural/) (1996), specifically chapter 10 [The Complexity of Learning](https://page.mi.fu-berlin.de/rojas/neural/chapter/K10.pdf), a book by Raul Rojas
  * [Complexity Analysis of Multilayer Perceptron Neural Network Embedded into a Wireless Sensor Network](https://core.ac.uk/download/pdf/82200790.pdf) (2014) by Gursel Serpen and Zhenning Gao, published in Complex Adaptive Systems
  * [On the Computational Efficiency of Training Neural Networks](https://papers.nips.cc/paper/5267-on-the-computational-efficiency-of-training-neural-networks.pdf) (2014) by Roi Livni, Shai Shalev-Shwartz and Ohad Shamir, published in NIPS 2014
  * [Convolutional Neural Networks at Constrained Time Cost](https://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/He_Convolutional_Neural_Networks_2015_CVPR_paper.pdf) (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](https://arxiv.org/pdf/1709.06010.pdf) (2018) by Surbhi Goel and Adam Klivans
  
  However, note that gradient descent (and other optimization algorithms) and the [back-propagation algorithm](http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Fall.2016/pdfs/Werbos.backprop.pdf) are [numerical algorithms](https://en.wikipedia.org/wiki/Numerical_analysis) (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.
  
  
  ---
  
  