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.