the manuscript is structured as follows. In Section \[sec:2\] we review the literature while in Section \[sec:3\] we present the theoretical results on how mini-batch sizes impact the variance of stochastic gradient estimators, under different models including linear regression and deep linear networks. Section \[sec:4\] introduces the experiments that verify our theorems and provide further insights into the impact of the mini-batch sizes on SGD performance. We defer the proofs of the theorems and other technical details to Appendix A and experimental details to Appendix B.

Literature Review {#sec:2}
=================

Stochastic gradient descent type methods are broadly used in machine learning [@bottou1991stochastic; @lecun1998gradient; @bottou2018optimization]. The performance of SGD highly relies on the choice of the mini-batch size. It has been widely observed that choosing a large mini-batch size to train deep neural networks appears to deteriorate generalization [@lecun2012efficient]. This phenomenon exists even if the models are trained without any budget or limits, until the loss function value ceases to improve [@keskar2019large]. One explanation for this phenomenon is that large mini-batch SGD produces “sharp” minima that generalize worse [@hochreiter1997flat; @keskar2019large]. Specialized training procedures to achieve good performance with large mini-batch sizes have also been proposed [@hoffer2017train; @goyal2017accurate].

It is well-known that 