decreasing function of the mini-batch size for a large enough value. Here samples are drawn from a normal distribution. As a special case, the variance of the stochastic gradient estimators is also a decreasing function for large enough mini-batch size, for all iterations and all choices of learning rates (Theorem \[thm:varianceRepresentation\]) that are independent of the mini-batch size. The proof can be easily extended to more than two layers.

-   In the two-layer network we also show that the variance is a polynomial in $1/b$. In order to establish all of the results we design a new proof technique where the main idea is to show a more general result than only considering variance in order to apply induction in a non-trivial way.

-   We verify the theoretical results on various datasets and provide further understanding. We further empirically show that the results extend to other widely used network structures and hold for all choices of the mini-batch sizes. We also empirically verify that, on average, in each iteration the loss function value and the generalization ability (measured by the gap between accuracy on the training and test sets) are all decreasing functions of the mini-batch size.

The rest of 