How does Batch Normalization in Machine Learning address covariate shift and speed up training? In this video and this answer, it's mentioned that batch normalization doesn't allow the mean and variance of the parameters of any particular hidden layer to vary too much with change in previous layer's node values. Let's say we have a network like this (taken from the video):

 

As we change the mini-batch that the neural network is trained on, it's possible that the distribution of the input features  with respect to different mini-batches is different. As far as I understand, this is called covariate shift. An issue with covariate shift is that maybe the distribution of input features with respect to the validation set examples is different from the training set (ref. black cats / colored cats example in the linked video), and the distributions w.r.t. the different mini-batches are different. 

Consequently, since the learned weights connecting the input layer to the next layer depend on the input features distribution, the learned weights will accordingly change with each mini-batch. Thus the activations in the next hidden layer will also vary in their distribution w.r.t. different mini-batches.

First question: Is my understanding so far correct?

Now I can understand that limiting the mean and variance of input features or that of the hidden layer activations will address the covariate shift problem only if the distributions across mini-batches (or between training and validation sets) are fundamentally the same but differ in parameters (not the neural network parameters - I mean mean and stddev). Crudely speaking, if the distribution of input features w.r.t different mini-batches is normal, but the parameters (mean and stddev) are different, then batch normalization seems fine.

Question 2: But what if the input features have normal distribution w.r.t. one mini-batch and a completely different distribution w.r.t. another? I don't see how limiting the mean and variance will help. Maybe I'm ignoring some key assumptions.

Question 3: Why does limiting the variation in the distributions of the hidden layers speed up the convergence?
So for the first question, you are almost correct. Your description of covariate shift is correct, but batch normalization isn't focused on fixing input layer covariate shift, but instead internal covariate shift. It's not a huge difference, since the internal covariate shift of a hidden layer acts as the input to another layer, but internal covariate shift can occur even if there isn't significant input layer covariate shift. 

The internal shift happens when weight updates occur while learning, after a couple epochs the output distribution of a hidden layer will likely change. This slows learning, because now the next hidden layer will have to learn the new distribution. Batch normalization tries to minimize this change in distribution so that less of the learning is focused on trying to learn the changes in hidden layer distributions.