How in the world is this "pretty practical"? It would be if people used this theorem to come up with an idea of SGD, but that's not what happened. SGD appeared as a way to overcome the practical constraint of computing full GD. Not to mention that "polynomial time" is meaningless to any practitioner.
it did come with a new online update for orthogonal tensor decomposition using higher order moments and with comments on NP-hardness for 4th order and higher.
In addition, it came with tricks with how much noise to inject in certain situations. "How much noise do you need is enough to escape?" which is pretty practical
