References for the computational complexity of training neural networks
See the papers by Roi Livni and coauthors:

*Roi Livni, Daniel Carmon, Amir Globerson:
Learning Infinite Layer Networks Without the Kernel Trick. ICML 2017: 2198-2207

*Roi Livni, Shai Shalev-Shwartz, Ohad Shamir:
On the Computational Efficiency of Training Neural Networks. NIPS 2014: 855-863