What are some resources regarding the complexity of training 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.