is Batch Norm a little bit stochastic by default? Using full-batch gradient descent, stacking 100 layers and using alpha 0.0001 results in steadily decreasing error.

However, after I implemented Batch Norm, the same scenario results in fluctuations. My implementation was verified by several people, so now I am wondering - why batch norm adds this stochastisity effect?

In fact, I am no longer able to stack 100+ layers, only approximatelly 10 layer before stochasticity becomes very apparent and hard to control.



What's more interesting -it seems to get worse with smaller learning rate! 0.4 is good, and 0.0001 results in smaller updates (as expected) but larger relative fluctuation (caught me by surprise).

Why is it so?

Edit: Just tried 100 layers (each 63 neurons). It's very noisy, but I am able to more-or-less steadily reduce the error. It's less stochastic if I set learning rate to 10 ("ten", lol!) and will get only noisier if it's say 0.5 which is incredibly weird

Of course, this learning rate is so high that the error does occasionally snap to a high value, but seems to work with 100 layers...

Notice - I am using full-batch gradient descent, with 50 elements



Edit:

Using 100 LSTM units, stacked like a pillar onto each other. 

Number of timesteps is 50. Feature size 50 (lstm state has dimension of 50), because my sentence has 50 distinct characters, each character is encountered only once per epoch. 

Performing backpropagation after 50 timesteps Using vanilla gradient descent, all fancy things like accelerated momentum or L2 norm, dropout are disabled. 

I am sure there is no error, but interested if anyone can tell why Batch Norm has this stochastic property, if that's common with people.
While I am no expert in batch normalization, I have noticed that in the paper they include a constant, epsilon (ε) to the minibatch variance for numerical stability (in the normalize step from this paper, page 3). So while your math might be right and verified by others, the actual computation could still be wrong.

This issue appears here. The solution on the bottom is to add variance clipping.

And with a stab at why you might be seeing it more with smaller learning rates. Well that might be just because you're taking a lot more steps to get to the same accuracy so that's just many more steps of numerical instability.
EDIT: I now realize when you say full-batch gradient descent you mean you are doing the entire dataset before updating the weights (just standard gradient descent). This means that with a smaller learning rate you will have to be doing more steps... so I'm sure that explains the learning rate difference.