Why not use alternating minimization for training neural networks? Neural networks are usually trained by calculating gradients using backprop and then performing gradient descent. I am not sure what are difficulties in training a neural network using alternating minimization?
Also, what is the order of computing gradient using backprop vs. naive gradient computation in neural networks?
Edit: It seems that the main idea in neural networks is that there are many parameters, and updates can be performed in parallel, thus speeding up the process. In this process, we lose the theoretical guarantees of alternating minimization, but we gain on speed. Is that right? What is the difference from a theoretical and optimization point of view of updating everything at once and serially?
Alternating minimization- In this optimization strategy, the idea is to fix everything except one variable and perform gradient descent for it, and do this procedure alternatively for all variables till some convergence criteria is met. Reference: https://www.mit.edu/~rakhlin/6.883/lectures/lecture07.pdf

I assume that by alternating minimization you mean optimizing over one layer while keeping the others fixed, and then repeating this process. This is also called block coordinate descent (coordinate descent being the setting in which we minimize over each variable one at a time).
A critical flaw of coordinate descent methods is that they need not converge to a stationary point. See the limitations section of this Wikipedia article on Coordinate Descent. This is worse that the situation for stochastic gradient descent, where you converge to a local minima. This is one reason why coordinate descent isn't used to train neural networks--even in small examples. It only works in special cases, and the gnarly objective functions produced when training neural networks isn't one of those cases.
