10x speedup in training is a huge deal since modern nets take 2-3 weeks to train on 4 GPUs. Note that the speedup is not actually in the forward-backward raw speed of the computation in the network. The speedup here is a more clever form of the forward function, which makes it converge faster as you train it. In fact, they have made the network slower in this paper because they added the normalization computation into it.
At test time (once training is finished), they are very efficient though, on orders of milliseconds per image.
(responding here because your comment addresses the actual new content of the paper).
Four things pop out at me from the paper:
1) The whitening (per batch) & rescaling (overall) is a neat new idea. But (as referred to in their p5 comment about the bias term being subsumed) this also points to the idea that the (Wu+b) transformation probably has a better-for-learning 'factorization', since their un-scale/re-scale operation on (Wu+b) is mainly taking out such a factor (while also putting in the minibatch accumulation change).
2) The idea that this could replace Dropout as the go-to trick for speeding up learning is pretty worrying (IMHO), since the gains from Dropout seem to be in a 'meta network' direction, rather than a data-dependency direction. Both approaches seem well worth understanding more thoroughly, even though the 'do what works' ML approach might favour leaving Dropout behind.
3) The publication of this paper, so closely behind the new ReLu+ results from Microsoft, seems too coincidental. One has to wonder what other results each of the companies has in their back-pockets so that they can repeatedly steal the crown from each other.
4) For me, the application to MNIST is attention-grabbing enough. While I appreciate that playing with Inception (etc) sexes-up the paper a lot, it raises the hurdle for others who may not have that quantity of hardware to contribute to the (more interesting) project of improving the learning rates of all projects (which is quite possible to do on the MNIST dataset, except that it's pretty much 'solved' with the error cases being pretty questionable for humans too).
At test time (once training is finished), they are very efficient though, on orders of milliseconds per image.